Minimum Shelves

You are given a maximum shelf width \(W\) and a list of parcel widths \(w_1, w_2, \dots, w_n\). The parcels are placed on shelves in the given order. For each shelf, the total width of the parcels on that shelf cannot exceed \(W\); in other words, if a shelf holds parcels with widths \(w_{i_1}, w_{i_2}, \dots, w_{i_k}\), then it must satisfy \(w_{i_1} + w_{i_2} + \dots + w_{i_k} \le W\).

Your task is to compute the minimum number of shelves required to store all the parcels.

inputFormat

The first line contains a single integer \(W\), the maximum allowed width per shelf.

The second line contains space-separated integers representing the widths of the parcels in order.

outputFormat

Output a single integer – the minimum number of shelves required.

10
2 3 5 8 2 1

3