Minimum Number of Shelves

You are given a list of boxes where each box has a certain weight, and a shelf that can hold a maximum weight. Your task is to determine the minimum number of shelves required to store all the boxes. The boxes must be arranged on the shelves such that the sum of the weights on any shelf does not exceed the given capacity.

Problem Details:

• You are given an integer n representing the number of boxes.
• A second integer capacity represents the maximum weight that a single shelf can support.
• The next line contains n integers where each integer represents the weight of a box.

Fill the shelves by arranging the boxes using a greedy approach: sort the boxes in descending order and then assign them to the current shelf if they fit; otherwise, start a new shelf.

Mathematical Formulation:

If the weights of boxes are given by \(w_1, w_2, \dots, w_n\), and each shelf can hold a total weight of \(C\), you need to minimize the number of shelves \(S\) such that the boxes can be partitioned into \(S\) groups each with a sum not exceeding \(C\).

inputFormat

The input is given via stdin in the following format:

n capacity
w1 w2 ... wn

Where:

• n (integer) is the number of boxes. If n is 0, there will be no weights provided.
• capacity (integer) is the maximum weight allowed on a shelf.
• w1, w2, ..., wn are the integers representing the weights of the boxes.

outputFormat

The output should be a single integer printed to stdout representing the minimum number of shelves required to store all the boxes.

## sample

6 10
4 8 1 4 2 1

3