7405: Tandem Bicycle(Problem J5)
题目描述
Since time immemorial, the citizens of Dmojistan and Pegland have been at war. Now, they have finally signed a truce. They have decided to participate in a tandem bicycle ride to celebrate the truce. There are N citizens from each country. They must be assigned to pairs so that each pair contains one person from Dmojistan and one person from Pegland.
Each citizen has a cycling speed. In a pair, the fastest person will always operate the tandem bicycle while the slower person simply enjoys the ride. In other words, if the members of a pair have speeds a and b, then the bike speed of the pair is max(a,b). The total speed is the sum of the N individual bike speeds.
For this problem, in each test case, you will be asked to answer one of two questions:
- Question 1: what is the minimum total speed, out of all possible assignments into pairs?
- Question 2: what is the maximum total speed, out of all possible assignments into pairs?
输入
The first line will contain the type of question you are to solve, which is either 1 or 2.
The second line will contain N (1≤N≤100).
The third line will contain N space-separated integers: the speeds of the citizens of Dmojistan.
The fourth line will contain N space-separated integers: the speeds of the citizens of Pegland.
Each person's speed will be an integer between 1 and 1000000.
For 8 of the 15 available marks, questions of type 1 will be asked. For 7 of the 15 available marks, questions of type 2 will be asked.
输出
样例输入 复制
1
3
5 1 4
6 2 4
样例输出 复制
12
提示
There is a unique optimal solution:
- Pair the citizen from Dmojistan with speed 5 and the citizen from Pegland with speed 6.
- Pair the citizen from Dmojistan with speed 1 and the citizen from Pegland with speed 2.
- Pair the citizen from Dmojistan with speed 4 and the citizen from Pegland with speed 4.