时间限制

1.0 s

内存限制

512.0 MB

题目描述

小A有2n件物品，小B和小C想从小A手上买走这些物品。对于第i件物品，小B会以b_i的价格购买，而小C会以c_i的价格购买。为了平均分配这2n件物品，小A决定小B和小C各自只能买走恰好n件物品。你能帮小A求出他卖出这2n件物品所能获得的最大收入吗？

输入格式

1. 第一行：一个正整数n。
2. 第二行：2n个整数b_1, b2, ..., b{2n}。
3. 第三行：2n个整数c_1, c2, ..., c{2n}。

   输出格式

   一行，一个整数，表示最大收入。

   样例

   输入样例1

   3
   1 3 5 6 8 10
   2 4 6 7 9 11

   输出样例1

   36

   输入样例2

   2
   6 7 9 9
   1 2 10 12

   输出样例2

   35

   数据范围

• 对于20%的测试点，保证1 ≤ n ≤ 8。
• 对于另外20%的测试点，保证0 ≤ b_i ≤ 1，0 ≤ c_i ≤ 1。
• 对于所有测试点，保证1 ≤ n ≤ 10^5，0 ≤ b_i ≤ 10^9，0 ≤ c_i ≤ 10^9。