You have a cassette with t seconds of length, and n songs with lengths d_{1}, d_{2}, …, 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}, …, d_{n}. You can assume 1 ≤ t ≤ 10^{8}, n ≥ 1, and that for each i, 1 ≤ d_{i} ≤ 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.
Input
11 5 2 2 2 2 2 10 5 2 2 2 2 2 100 1 101 1000 3 17 1 17
Output
4 3 0 3