#P18167. Price Combo
Price Combo
Price Combo
Czesaw 决定自己组装电脑。他列出了一张包含 个配件的清单。
附近有两家电子商店:AutoAGD 和 BioBezpieczniki。清单上第 个配件在 AutoAGD 的价格为 PLN,在 BioBezpieczniki 的价格为 PLN。两家店各自独立地提供“买一送一”活动:一次购买两件商品时,较便宜的那件免费(价格相同则任意)。活动次数不限,同一顾客可以在同一家店多次享受该活动。
允许单独购买一件商品并支付其价格;不要求所有商品都参加配对促销。每件清单上的配件恰好购买一次。
请帮助 Czesaw 以最低总价买齐所有配件,输出最小总花费。
输入格式
第一行一个整数 ()。
第二行 个整数 ()。
第三行 个整数 ()。
输出格式
输出一个整数,表示最小总花费。
样例
输入:
7
10 12 19 99 10 8 49
9 14 15 199 11 7 19
输出:
131
样例解释:在 AutoAGD 将第 1、5 件配对支付 10,第 4、7 件配对支付 99;在 BioBezpieczniki 将第 2、3 件配对支付 15,第 6 件单独购买支付 7,总计 131。