Packing Books into Boxes

Interview

Time limit2sMemory limit128 MB

Summary

Given book weights in order and a per-box weight limit, compute the minimum number of boxes needed by greedily filling each box in sequence.

Level: Easy2 of 10
Topics: Greedy, Array, Simulation
Solved: No attempts yet

Problem

A pile of books is stacked like a tower, and you want to pack them into boxes to ship. Because the books are stacked in order, you can only take them one at a time from the top and place them into boxes in that exact order.

Each book has a weight, and each box can hold books whose total weight is at most M. Packing the books in their stacked order, write a program that finds the minimum number of boxes needed.

Input

The first line contains the number of books N and the maximum weight M a single box can hold. N is an integer with 0 ≤ N ≤ 50, and M is a natural number with M ≤ 1000. If N is greater than 0, the second line contains the weights of the books in stacking order, separated by spaces. Each book's weight is a natural number not greater than M.

Output

Print the minimum number of boxes needed on the first line.

Examples5

Example 1
Input
```
6 10
5 5 5 5 5 5
```
Expected output
```
3
```
Example 2
Input
```
5 100
51 51 51 51 51
```
Expected output
```
5
```
Example 3
Input
```
6 8
1 1 1 7 7 7
```
Expected output
```
4
```
Example 4
Input
```
11 12
12 1 11 2 10 3 4 5 6 6 1
```
Expected output
```
6
```
Example 5
Input
```
0 7
```
Expected output
```
0
```