2013 Canadian Computing Competition, Stage 1

Problem S2: Bridge transport

A train of railway cars attempts to cross a bridge. The length of each car is 10 m but their weights might be different. The bridge is 40 m 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…T (in order) can cross the bridge?

Input

The first line of input is the maximum weight W (1 ≤ W ≤ 100000) that the bridge can hold at any particular time. The second line of input is the number N (1 ≤ N ≤ 100000) 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 ≤ i ≤ N, 1 ≤ w_i ≤ 100000) which represents the weight of the i^th railway car in the sequence.

Output

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

Sample Output 1

5

Explanation

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

Sample Output 2

0

Explanation

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.

All Submissions
Best Solutions

Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: May 19, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The new server seems to be slower than the old one...
Also, when I submitted two identical submissions, one ACed, and the other one had one test case WA and one test case TLE...

Please provide submission IDs so I can investigate.

93471 and 93472

Use raw_input() instead of input()