1324 - 两地调度

公司计划面试 2n 人。给你一个数组 costs ,其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ,飞往 b 市的费用为 bCosti

返回将每个人都飞到 ab 中某座城市的最低费用,要求每个城市都有 n 人抵达。

输入

第一行为一个整数2n,表示有2n个人面试

以下2n行,每行2个整数,第一个整数为去a市的费用,第二个证书为去b市的费用

输出

每个城市都有 n 人抵达的最低费用

样例

输入

4
10 20
30 200
400 50
30 20

输出

110

输入

6
259 770
448 54
926 667
184 139
840 118
577 469

输出

1859

输入

8
515 563
451 713
537 709
343 819
855 779
457 60
650 359
631 42

输出

3086

提示

  • 2 * n == costs.length

  • 2 <= costs.length <= 100

  • costs.length 为偶数

  • 1 <= aCosti, bCosti <= 1000

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题