Remember the Cookie Clicker Craze last year? Now that it is pretty much over (or is it?), Peanut is playing Cookie Clicker alone at home. With no one else competing for the number of cookies baked, Peanut creates his own variant of the Cookie Clicker game. In this new variant of Cookie Clicker, there are P different powerups that Peanut can buy, each costing 1 cookie. Each of these powerups also add a certain amount of CpS to Peanut's game. However, there is a catch. Every time a powerup gets bought and used, the number of CpS gained from this powerup decreases by 10%, rounded down to the nearest integer.
For example, if a certain powerup that gives you 6 CpS is bought, the next time you buy and use this powerup, you will only gain 6 x 0.9 = 5.4 = 5 (rounded down) CpS. The next time you use this powerup, you will gain 5 x 0.9 = 4.5 = 4 CpS, and so on. Given the number of cookies Peanut has to spend, N, the number of powerups Peanut can use, P, and the starting CpS gain for each powerup, find out the maximum CpS Peanut can achieve with N cookies to spend.
The first line of input will contain two integers, N
The second line of input will contain P
integers, with the i
th integer representing the starting CpS of the i
Your output should contain one integer, the maximum CpS Peanut can gain.
The starting CpS gained from each powerup will always be less than 231
Subtask 1 (19%): 1 ≤ N, P ≤ 100.
Subtask 2 (24%): 1 ≤ N, P ≤ 1000.
Subtask 3 (28%): 1 ≤ N, P ≤ 100000.
Subtask 4 (29%): 1 ≤ N ≤ 231
-1. 1 ≤ P ≤ 100000.
Subtask 5 (0%): As per sample testcases.
Sample Input 1
1 2 3 4
Sample Output 1
Sample Input 2
1 1 1
Sample Output 2