У Медузы есть \(n\) зеленых яблок со значениями \(a_1, a_2, \dots, a_n\), а у Гедузы есть \(m\) зеленых яблок со значениями \(b_1,b_2,\ldots,b_m\).
Они будут играть в игру, состоящую из \(k\) раундов. Для \(i=1,2,\ldots,k\) в этом порядке они будут выполнять следующие действия:
- Если \(i\) нечетное, то Медуза может поменять одно свое яблоко на одно яблоко Гедузы или ничего не делать.
- Если \(i\) четное, то Гедуза может поменять одно из своих яблок на одно из яблок Медузы или ничего не делать.
Оба игрока хотят максимизировать сумму стоимостей своих яблок.
Поскольку вы — один из самых умных людей в мире, Медуза хочет, чтобы вы сообщили ей окончательную сумму стоимости ее яблок после всех \(k\) раундов игры. Предположим, что и Медуза, и Гедуза играют оптимально, стремясь максимизировать сумму стоимостей своих яблок.
Выходные данные
Для каждого набора входных данных выведите одно целое число — конечную сумму значений яблок Медузы.
Примечание
В первом наборе входных данных Медуза поменяет местами яблоки стоимостью \(1\) и \(4\).
Во втором наборе входных данных оба игрока поменяют местами два яблока \(10,000\) раз.
В четвертом наборе входных данных Медуза ничего не будет делать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 2 1
1 2
3 4
1 1 10000
1
2
4 5 11037
1 1 4 5
1 9 1 9 8
1 1 1
2
1
|
6
1
19
2
|