Ferry Loading

You are given a ferry with a fixed length L. Vehicles arrive in a fixed order with given lengths, and the ferry must transport them across the river using the minimum number of trips. For each trip, vehicles are loaded in order until adding the next vehicle would exceed the ferry’s length. When that happens, the ferry departs and a new trip begins. The process continues until all vehicles have been loaded.

Note: Input is provided from standard input (stdin) and output should be printed to standard output (stdout). The input ends when a test case with L = 0 and N = 0 is encountered.

Example: Suppose the ferry length is 10 and vehicles have lengths [4, 4, 4, 4]. The first three vehicles can be loaded in one trip (4 + 4 + 4 = 12 would exceed the limit, so only two 4’s can be taken and then a new trip is required) resulting in 2 trips in total.

inputFormat

The input consists of several test cases. Each test case starts with a line containing two integers L and N, where L is the length of the ferry and N is the number of vehicles. The next line contains N space-separated integers representing the lengths of the vehicles in order. The input terminates with a test case where L = 0 and N = 0, and this test case should not be processed.

outputFormat

For each test case (except the terminating one), output a single integer on a new line indicating the minimum number of trips required to transport all vehicles across the river.

## sample

10 4
4 4 4 4
10 5
6 5 4 3 2
15 3
6 7 5
0 0

2
3
2

</p>