題目描述

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 contains N (1 ≤ N ≤ 100).

The third line contains N space-separated integers: the speeds of the citizens of Dmojistan.

The fourth line contains N space-separated integers: the speeds of the citizens of Pegland.

Each person’s speed will be an integer between 1 and 1 000 000.

輸出格式

Output the maximum or minimum total speed that answers the question asked.

Samples

["1\r\n3\r\n5 1 4\r\n6 2 4","2\r\n3\r\n5 1 4\r\n6 2 4","2\r\n5\r\n202 177 189 589 102\r\n17 78 1 496 540"]

["12","15","2016"]

提示

sort()

原始資料

• Zero1 題號：a881
• Hydro 題號：Z0881
• Locale：zh_TW
• Display：open