Cassette P65849

You have a cassette with $t$ seconds of length, and $n$ songs with lengths $d_1, d_2, \dots, d_n$. Your aim is to store the maximal number of whole songs in the cassette. You must consider that songs must be recorded with a second of separation between them.

Input

The input consists of a series of cases separated with a line in white. Each case consists of two lines: The first one has $t$ and $n$. The second one has $n$ numbers: $d_1, d_2, \dots, d_n$. You can assume $1 \le t \le 10^8$, $n \ge 1$, and that for each $i$, $1 \le d_i \le 10^6$.

Output

For each case of the input, your program must print the maximal number of whole songs that fit in the cassette, bearing that they must be separated by a second in mind.

• TestA:   In some test cases $n \le 100$ will be fulfilled.

• TestB:   Other test cases will include cases with $n \le 10^5$.