Козак Вус та крамниця#10355

Козак Вус та крамниця

1 секунда

256 мегабайтів

Дуже легка

Переїхавши у велике місто, Козак Вус вирішив, що йому слід зайнятись малим бізнесом, тому відкрив невеличку ювелірну крамницю. У нього є $n$ ювелірних виробів, ціна $i$ -го з них рівна $a_{i}$ a_i.

Але внаслідок епідемії продаж ювелірних виробів знизився, тому Козак Вус вирішив зробити акційний розпродаж. За умовами акції, покупець може:

Вибрати деяке додатне число $k$ .
Придбати усі $m$ ювелірних виробів з ціною не менше, ніж $k$ , за $k \cdot m$ k \cdot m монет загалом. Іншими словами, кожен виріб, у якого $a_{i} \geq k$ a_i \geq k, він купить за $k$ .

Тепер Козак Вус зацікавився, якою буде максимальна сума, виплачена за акційною пропозицією.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) — кількість ювелірних виробів у Козака Вуса.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $1 \leq a_{i} \leq 1 0^{9}$ 1 \leq a_i \leq 10^9) — ціна $i$ -го виробу.

Вихідні дані

Виведіть єдине ціле число — максимальну кількість монет, яку може отримати Козак Вус за цією акцією, яка рівна максимальному значенню $k \cdot m$ k \cdot m, де $k$ — деяке додатне ціле число, $m$ — кількість ювелірних виробів $i$ таких, що $k \leq a_{i}$ k \leq a_i.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі можна вибрати $k = 7$ k=7, для якого знайдуться $3$ вироби з ціною не менше за $k$ .

У другому прикладі можна вибрати $k = 6$ k=6 та купити всі.

Оцінювання

Кожен тест оцінюється окремо. Ви можете отримати $45$ балів на тестах, де $n, a_{i} \leq 1000$ n, a_i \leq 1000.