18331번 - 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.

입력

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

출력

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.

제한

힌트