Лелик и Болек едут за границу на самолете. Сейчас в местном аэропорте действует акция под названием «Выбери Самолет». Условия акции таковы:
- пассажир сам выбирает самолет, в котором он полетит;
- пусть в выбранном самолете на данный момент x (x > 0) свободных мест, тогда билет на такой самолет стоит x злотых.
Очередь из n пассажиров уже выстроилась перед единственной билетной кассой аэропорта. Лелик и Болек еще не встали в очередь, но им уже интересно: какое максимальное и минимальное количество злотых может заработать администрация аэропорта, если все n пассажиров будут покупать билеты по этой акции?
Пассажиры покупают билеты по очереди, сначала первый в очереди, потом второй, и так далее до n-го.
Выходные данные
Выведите два целых числа — максимальное и минимальное количество злотых, которое может заработать администрация аэропорта соответственно.
Примечание
В первом тестовом примере количество пассажиров равно количеству свободных мест, поэтому при любом выборе самолетов заработанная сумма будет одинаковая.
Во втором примере, чтобы максимизировать заработанную сумму 1-ый в очереди должен купить билет на 1-ый самолет, 2-ой в очереди — на 2-ой самолет, 3-ий в очереди — на 3-ий самолет, 4-ый в очереди — на 1-ый самолет. Чтобы минимизировать заработанную сумму 1-ый в очереди должен купить билет на 1-ый самолет, 2-ой в очереди — на 1-ой самолет, 3-ий в очереди — на 2-ий самолет, 4-ый в очереди — на 2-ый самолет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
2 1 1
|
5 5
|
|
2
|
4 3
2 2 2
|
7 6
|