З незапам'ятних часів громадяни Паскальстану та Сігланди ворогували. Тепер вони нарешті підписали перемир'я і вирішили взяти участь у велопробігу на честь перемир'я.

Є \(N\) громадян з кожної країни. Вони повинні бути розподілені по парах так, щоб кожна пара містила одну особу з Паскальстану та одну особу з Сігланди.

Кожен громадянин має свою швидкість руху на велосипеді. У парі найшвидша людина завжди керуватиме велосипедом-тандемом, а повільніша просто насолоджується поїздкою. Іншими словами, якщо члени пари мають швидкості \(a\) і \(b\), то швидкість велосипеда пари дорівнює \(max(a,b)\). Загальна швидкість є сумою індивідуальних швидкостей велосипедів.

Напишіть програму, що дасть відповіді на такі запити двох типів:

• 1: яка мінімальна загальна швидкість з усіх можливих розподілів на пари?
• 2: яка максимальна загальна швидкість з усіх можливих розподілів на пари?

Input

Перший рядок містить тип запитання, яке ви маєте розв'язати: 1 або 2.

Другий рядок містить ціле число \(N\) (\(1 \le N \le 100\)).

У третьому рядку через пропуски записані \(N\) цілих чисел - швидкості жителів Паскальстану.

У четвертому рядку через пропуски записані \(N\) цілих чисел - швидкості жителів Сігланди.

Швидкість кожної людини буде цілим числом від 1 до \(10^6\).

Output

Виведіть максимальну або мінімальну загальну швидкість, яка відповідає запиту 1 або 2.

Sample Input 1

1
3
5 1 4
6 2 4

Sample Output 1

12

Sample Input 2

2
3
5 1 4
6 2 4

Sample Output 2

15

Notes

До прикладу 1

Існує єдине оптимальне рішення:

• оберіть людей зі швидкостями 5 і 6
• оберіть людей зі швидкостями 1 і 2
• оберіть людей зі швидкостями 4 і 4