#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

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.

## Input

The first line of input will contain two integers,*N*and

*P*.

The second line of input will contain

*P*integers, with the

*i*th integer representing the starting CpS of the

*i*th powerup.

## Output

Your output should contain one integer, the maximum CpS Peanut can gain.## Limits

The starting CpS gained from each powerup will always be less than 2^{31}-1.

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 ≤ 2

^{31}-1. 1 ≤ P ≤ 100000.

Subtask 5 (0%): As per sample testcases.

## Sample Input 1

7 4 1 2 3 4

## Sample Output 1

17

## Sample Input 2

4 3 1 1 1

## Sample Output 2

3

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 19 | 20 | 1s | 32MB | Minimum |

2 | 24 | 40 | 1s | 32MB | Minimum |

3 | 28 | 60 | 1s | 32MB | Minimum |

4 | 29 | 80 | 3s | 32MB | Minimum |

5 | 0 | 2 | 1s | 32MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o cookieclicker -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512