High School Programming League Problems Archive

In the far far away land of Waste-a-lot, there is a very famous house in which people place bets on sports. Being a professional gambler, you noticed that, if you place bets on N specific events, you are guaranteed to win in at least one of them. Besides, you know how much money you will get per dollar placed on each of the N events.

Given that information and the amount of money you carry, you would like to know what is the lowest possible value of your earnings to be expected if you place bets in such a way that its minimum value is maximized (you can only bid an integer number of dollars on each event).

For instance, let's suppose you carry $100 and there are 3 events A, B and C.

• A: $3 per dollar placed
• B: $5 per dollar placed
• C: $7 per dollar placed

Then, you would place $49 on event A, $30 on event B and $21 on event C. As 49 * $3 = $147, 30 * $5 = $150 and 21 * $7 = $147 you know you will leave the house with, at least, $147; thus earning $47.

Input

Input starts with two space-separated integers 1<=M<=10^6 and 1<=N<=100, the amount of money you carry and the number of events respectively.

The second line contains N space-separated integers (2<=A_i<=1000), how much will you earn per dollar placed on each event.

Output

Print the sought value on a single line.

Example

Input:
100 3
3 5 7

Output:
47

Scoring

By solving this problem you score 10 points.