В кафе пришли \(n\) клиентов. Каждый из них хочет купить по одному гамбургеру. У \(i\)-го клиента с собой \(a_i\) монет, и он купит гамбургер в том случае, если гамбургер стоит не более \(a_i\) монет.
Пусть стоимость гамбургера равна \(m\). Тогда прибыль кафе — это произведение \(m\) и количества людей, готовых купить гамбургер за \(m\) монет. Ваша задача — подсчитать максимально возможную прибыль кафе, если стоимость гамбургера будет выбрана оптимально.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможную прибыль кафе.
Примечание
Объяснение примера:
- наилучшая цена гамбургера равна \(m = 1\); в таком случае будут куплены \(3\) гамбургера, и прибыль составит \(3\) монеты;
- наилучшая цена гамбургера равна \(m = 4\); в таком случае будет куплен \(1\) гамбургер, и прибыль составит \(4\) монеты;
- наилучшая цена гамбургера равна \(m = 2\); в таком случае будут куплены \(3\) гамбургера, и прибыль составит \(6\) монет;
- наилучшая цена гамбургера равна \(m = 4\); в таком случае будут куплены \(5\) гамбургера, и прибыль составит \(20\) монет;
- наилучшая цена гамбургера равна \(m = 10^{12}\); в таком случае будет куплен \(1\) гамбургер, и прибыль составит \(10^{12}\) монет;
- наилучшая цена гамбургера равна \(m = 10^{12} - 1\); в таком случае будут куплены \(2\) гамбургера, и прибыль составит \(2 \cdot 10^{12} - 2\) монет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
1 1 1
3
4 1 1
3
2 4 2
8
1 2 3 4 5 6 7 8
1
1000000000000
3
1000000000000 999999999999 1
|
3
4
6
20
1000000000000
1999999999998
|