Canadian Computing Competition: 2013 Stage 1, Senior #2

A train of railway cars attempts to cross a bridge. The length of each car is 10m but their weights might be different. The bridge is 40m long (thus can hold ~4~ train cars at one time). The bridge will crack if the total weight of the cars on it at one time is greater than a certain weight. The cars are numbered starting at ~1~, going up to ~N~, and they cross the bridge in that order (i.e., ~1~ immediately followed by ~2~, which is immediately followed by ~3~, and so on).

What is the largest number ~T~ of railway cars such that the train of cars ~1 \dots T~ (in order) can cross the bridge?

Input Specification

The first line of input is the maximum weight ~W~ (~1 \le W \le 100\,000~) that the bridge can hold at any particular time. The second line of input is the number ~N~ (~1 \le N \le 100\,000~) which is the number of railway cars that we wish to move across the bridge. On each of the next ~N~ lines of input, there will be a positive integer ~w_i~ (~1 \le i \le N~, ~1 \le w_i \le 100\,000~) which represents the weight of the ~i^{th}~ railway car in the sequence.

Output Specification

Your output should be a non-negative integer representing the maximum number of railway cars that can be brought across the bridge in the order specified.

Sample Input 1

100
6
50
30
10
10
40
50

Output for Sample Input 1

5

Explanation of Output for Sample Input 1

The first four railway cars have total weight ~50 + 30 + 10 + 10 = 100~, which is not greater than what the bridge can hold. When the first railway car leaves, and the next comes on, we have a total weight of ~30 + 10 + 10 + 40 = 90~, which is not greater than what the bridge can hold. The last four cars would cause the bridge to break, since ~10 + 10 + 40 + 50 = 110~ which is greater than the bridge can hold. So, only the first ~5~ railway cars can be taken across the bridge.

Sample Input 2

100
3
150
1
1

Output for Sample Input 2

0

Explanation of Output for Sample Input 2

When the first railway car enters the bridge, its weight of ~150~ will exceed the maximum weight the bridge can hold. Thus, we cannot bring any railway cars across the bridge.