#P18167. Price Combo

Price Combo

Price Combo

Czesaw 决定自己组装电脑。他列出了一张包含 NN 个配件的清单。

附近有两家电子商店:AutoAGD 和 BioBezpieczniki。清单上第 ii 个配件在 AutoAGD 的价格为 AiA_i PLN,在 BioBezpieczniki 的价格为 BiB_i PLN。两家店各自独立地提供“买一送一”活动:一次购买两件商品时,较便宜的那件免费(价格相同则任意)。活动次数不限,同一顾客可以在同一家店多次享受该活动。

允许单独购买一件商品并支付其价格;不要求所有商品都参加配对促销。每件清单上的配件恰好购买一次。

请帮助 Czesaw 以最低总价买齐所有配件,输出最小总花费。

输入格式

第一行一个整数 NN(1≤N≤2⋅1051\le N\le 2\cdot10^5)。

第二行 NN 个整数 A1,…,ANA_1,\dots,A_N(1≤Ai≤1091\le A_i\le10^9)。

第三行 NN 个整数 B1,…,BNB_1,\dots,B_N(1≤Bi≤1091\le B_i\le10^9)。

输出格式

输出一个整数,表示最小总花费。

样例

输入:

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。