Farmer John планирует открыть новый университет для коров!
В этом университете потенциально могут учиться $N$ коров ($1 \le N \le 10^5$). Каждая корова готова заплатить за обучение не более $c_i$ ($1 \le c_i \le 10^6$). Farmer John может установить плату за обучение, которую должны заплатить все коровы для поступления. Если эта плата превышает максимум, который готова заплатить корова, то она не будет учиться в университете. Farmer John хочет заработать как можно больше денег, чтобы платить своим преподавателям справедливую зарплату. Определите, сколько денег он может заработать и какую плату за обучение ему следует установить.
Входные данные
Первая строка содержит $N$. Вторая строка содержит $N$ целых чисел $c_1, c_2, \dots, c_N$, где $c_i$ — максимальная плата за обучение, которую готова заплатить корова $i$.
Выходные данные
Выведите максимальную сумму, которую может заработать Farmer John, и оптимальную плату за обучение. Если существует несколько решений, выведите решение с наименьшей оптимальной платой за обучение.
Обратите внимание, что из-за большой величины целых чисел в этой задаче может потребоваться использование 64-битных целочисленных типов (например, "long" в Java или "long long" в C/C++).
Примеры
Входные данные 1
4 1 6 4 6
Выходные данные 1
12 4
Примечание
Если Farmer John установит плату $4$, то учиться будут $3$ коровы, что позволит ему заработать $3 \cdot 4 = 12$.
Подзадачи
- В тестах со 2 по 4 выполняется $c_i \le 1{,}000$.
- В тестах с 5 по 8 выполняется $N \le 5{,}000$.
- Тесты с 9 по 12 не имеют дополнительных ограничений.
Автор задачи: Freddie Tang