B. Аэропорт
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лелик и Болек едут за границу на самолете. Сейчас в местном аэропорте действует акция под названием «Выбери Самолет». Условия акции таковы:

  • пассажир сам выбирает самолет, в котором он полетит;
  • пусть в выбранном самолете на данный момент x (x > 0) свободных мест, тогда билет на такой самолет стоит x злотых.

Очередь из n пассажиров уже выстроилась перед единственной билетной кассой аэропорта. Лелик и Болек еще не встали в очередь, но им уже интересно: какое максимальное и минимальное количество злотых может заработать администрация аэропорта, если все n пассажиров будут покупать билеты по этой акции?

Пассажиры покупают билеты по очереди, сначала первый в очереди, потом второй, и так далее до n-го.

Входные данные

В первой строке записано два целых числа n и m (1 ≤ n, m ≤ 1000) — количество пассажиров в очереди и количество самолетов в аэропорте соответственно. В следующей строке записано m целых чисел a1, a2, ..., am (1 ≤ ai ≤ 1000) — ai обозначает количество свободных мест в i-ом самолете перед началом продажи билетов.

Числа в строках разделяются пробелами. Гарантируется, что суммарное количество свободных мест не меньше, чем n.

Выходные данные

Выведите два целых числа — максимальное и минимальное количество злотых, которое может заработать администрация аэропорта соответственно.

Примеры
Входные данные
4 3
2 1 1
Выходные данные
5 5
Входные данные
4 3
2 2 2
Выходные данные
7 6
Примечание

В первом тестовом примере количество пассажиров равно количеству свободных мест, поэтому при любом выборе самолетов заработанная сумма будет одинаковая.

Во втором примере, чтобы максимизировать заработанную сумму 1-ый в очереди должен купить билет на 1-ый самолет, 2-ой в очереди — на 2-ой самолет, 3-ий в очереди — на 3-ий самолет, 4-ый в очереди — на 1-ый самолет. Чтобы минимизировать заработанную сумму 1-ый в очереди должен купить билет на 1-ый самолет, 2-ой в очереди — на 1-ой самолет, 3-ий в очереди — на 2-ий самолет, 4-ый в очереди — на 2-ый самолет.