Cossack Vus and the Shop#10355
After moving to a big city, Cossack Vus decided to start a small business by opening a jewelry store. He has pieces of jewelry, with the price of the -th piece being a_i.
Due to the epidemic, jewelry sales have declined, prompting Cossack Vus to launch a promotional sale. Under this promotion, a customer can:
Select a positive number .
Purchase all pieces of jewelry priced at least for a total of k \cdot m coins. This means each piece with a_i \geq k is bought for coins.
Cossack Vus wants to know the maximum amount he can receive from this promotional offer.
The first line contains a single integer (1 \leq n \leq 10^5) — the number of jewelry pieces Cossack Vus has.
The second line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9) — the price of the -th piece.
Output a single integer — the maximum number of coins Cossack Vus can earn from this promotion, which is the maximum value of k \cdot m, where is a positive integer, and is the number of jewelry pieces such that k \leq a_i.
Example 1
Example 2
In the first example, you can choose k=7, for which there are pieces with a price not less than .
In the second example, you can choose k=6 and buy all.
Each test is scored separately. You can earn points on tests where n, a_i \leq 1000.