На доске записано \(2n\) целых положительных чисел. От скуки вы решили сыграть в одиночную игру с числами на доске.
Вы начинаете игру со счетом \(0\). Вы увеличите свой счет, выполняя следующую операцию ровно \(n\) раз:
- Выбрать два целых числа \(x\) и \(y\), которые записаны на доске.
- Прибавить \(\min(x,y)\) к своему счету.
- Стереть \(x\) и \(y\) с доски.
Обратите внимание, что после того, как вы выполните этот ход \(n\) раз, на доске больше не будет записано ни одного числа.
Найдите максимальный итоговый счет, который вы можете получить, если оптимально выполните \(n\) ходов.
Выходные данные
Для каждого набора входных данных выведите максимальный итоговый счет, который вы можете получить.
Примечание
В первом наборе входных данных вы можете сделать только один ход. Вы выбираете \(x=2\) и \(y=3\), и ваш счет будет \(\min(x,y)=2\).
Во втором наборе входных данных ниже приведена последовательность ходов, которая позволяет получить итоговый счет \(2\):
- На первом ходу выберите \(x=1\) и \(y=1\). Затем добавьте к счету \(\min(x,y)=1\). После стирания \(x\) и \(y\) на доске останутся целые числа \(1\) и \(2\).
- На втором ходу выберите \(x=1\) и \(y=2\). Затем добавьте к счету \(\min(x,y)=1\). После удаления \(x\) и \(y\) на доске больше не останется целых чисел.
Можно доказать, что получить счет больше
\(2\) невозможно.
В третьем наборе входных данных выполните ход трижды, каждый раз прибавляя к счету \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
2 3
2
1 1 2 1
3
1 1 1 1 1 1
|
2
2
3
|