Gold Rush

Again, Neverland has experienced a very bad economic condition over the past few months. The value of Oshloob, the national currency of Neverland, changes against one unit of gold very rapidly. People in Neverland, all wondering about their savings, are trying to exchange their savings with gold coins.

Dr. Predictman who is a data scientist, has obtained a prediction of the price (in Oshloobs) of a gold coin for the next $N$ days based on the existing data over the past 40 years. He believes his prediction, and now he want to increase his savings based on it. He was wondering how much savings he has at the end of the n-th day assuming that he has $C$ Oshloobs at the beginning of the first day. Since Dr. Predictman is not a programmer, he asks you to help to find his answer.

Input

The first line of the input contains two integers $C \ (0 \leq C \leq 3000)$, Dr. Predictman’s initial savings in Oshloobs, and $N \ (0 \leq N \leq 30)$, the period of his prediction. Each of the next following $N$ lines contains an integer $p_i \ (1000 \leq p_i \leq 2000)$ denoting the price of a gold coin at day $i \ (1 \leq i \leq N)$ in Oshloobs.

Output

The output contains just an integer, which indicates the maximum savings he can obtain at the end of the n-th day assuming that Dr. Predictman exchanges all his remaining gold coins (if there is any) to Oshloobs at the end of the n-th day.