Ropes

Interview

Time limit2sMemory limit192 MB

Summary

Choose a subset of ropes so that each rope's capacity times the count of chosen ropes is maximized, to find the greatest liftable weight.

Level: Easy3 of 10
Topics: Sorting, Greedy
Solved: No attempts yet

Problem

There are N ropes (1 <= N <= 100,000). Each rope may support a different maximum weight because its thickness and length can differ.

If several ropes are connected in parallel, the total weight is divided evenly among the ropes being used. When k ropes lift an object of weight w, each rope supports w/k.

You may choose any nonempty subset of the given ropes. Determine the maximum object weight that can be lifted.

Input

The first line contains the integer N, the number of ropes.

Each of the next N lines contains the maximum weight that one rope can support. Each weight is a natural number not greater than 10,000.

Output

Print the maximum weight that can be lifted using the selected ropes.

Examples1

Example 1
Input
```
2
10
15
```
Expected output
```
20
```