e-olymp
Competitions

Ukrainian Olympiad in Informatics, III Stage, I Round

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

Переїхавши у велике місто, Козак Вус вирішив, що йому слід зайнятись малим бізнесом, тому відкрив невеличку ювелірну крамницю. У нього є $n$ ювелірних виробів, ціна $i$-го з них рівна $a_i$. Але внаслідок епідемії продаж ювелірних виробів знизився, тому Козак Вус вирішив зробити акційний розпродаж. За умовами акції, покупець може: \begin{itemize} \item Вибрати деяке додатне число $k$. \item Придбати усі $m$ ювелірних виробів з ціною не менше, ніж $k$, за $k \cdot m$ монет загалом. Іншими словами, кожен виріб, у якого $a_i \geq k$, він купить за $k$. \end{itemize} Тепер Козак Вус зацікавився, якою буде максимальна сума, виплачена за акційною пропозицією. \InputFile Перший рядок містить одне ціле число $n$ ($1 \leq n \leq 10^5$) --- кількість ювелірних виробів у Козака Вуса. Другий рядок містить $n$ цілих чисел $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) --- ціна $i$-го виробу. \OutputFile Виведіть єдине ціле число --- максимальну кількість монет, яку може отримати Козак Вус за цією акцією, яка рівна максимальному значенню $k \cdot m$, де $k$ --- деяке додатне ціле число, $m$ --- кількість ювелірних виробів $i$ таких, що $k \leq a_i$. \Note У першому прикладі можна вибрати $k=7$, для якого знайдуться $3$ вироби з ціною не менше за $k$. У другому прикладі можна вибрати $k=6$ та купити всі. \Scoring Кожен тест оцінюється окремо. Ви можете отримати $45$ балів на тестах, де $n, a_i \leq 1000$.
Time limit 1 second
Memory limit 256 MiB
Input example #1
5
3 10 5 7 8
Output example #1
21
Input example #2
4
6 6 6 6
Output example #2
24
Author Andrey Abdulaev