Фермер Джон планирует открыть новый университет для коров!
Имеется \(N\) (\(1 \le N \le 10^5\)) коров, которые потенциально могут посещать университет.
Каждая корова готова платить за обучение максимум \(c_i\) (\(1 \le c_i \le 10^6\)).
Фермер Джон может установить плату за обучение, которую все коровы должны оплатить.
Если эта плата больше, чем корова готова платить, она не платит и не учится в университете.
Фермер Джон хочет установить такую оплату, чтобы получить максимальную сумм оплат.
Определите эту максимальную сумму и установленную плату за обучение.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит \(N\). Вторая строка содержит \(N\) целых чисел \(c_1, c_2, \dots, c_N\),
где \(c_i\) - это максимальная плата, которую готова платить корова \(i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите максимальное количество денег, которое может получить ФД и оптимальную оплату
за обучение, которую он должен установить. Если имеется несколько вариантов, выберите тот
в котором минимальная оплата за обучение.
Заметим, что надо использовать 64-битный целый тип, например
"long" в Java, или "long long" в C/C++).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 6 4 6
|
12 4
|