Cassette P65849


Statement
 

pdf   zip

html

You have a cassette with t seconds of length, and n songs with lengths d1, d2, …, dn. 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: d1, d2, …, dn. You can assume 1 ≤ t ≤ 108, n ≥ 1, and that for each i, 1 ≤ di ≤ 106.

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 ≤ 100 will be fulfilled.  60 Points 
  • TestB:   Other test cases will include cases with n ≤ 105.  40 Points 
Public test cases

  • 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
    • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++