Minimum Containers

You are given (n) boxes with respective weights and an unlimited number of containers. Each container can hold boxes up to a weight limit of (w). The objective is to determine the minimum number of containers required such that the sum of the weights in each container does not exceed (w).

The boxes can be placed into containers in any order. A greedy approach by sorting the boxes in descending order and then placing them in a container if they fit often works well for this problem.

For example, consider 3 boxes with weights [3, 5, 7] and a container weight limit of 10. One optimal way is to put the boxes with weights 7 and 3 into one container (7+3=10) and the remaining box with weight 5 in a separate container, yielding a total of 2 containers.

inputFormat

The input is given via standard input (stdin) and is formatted as follows:

1. The first line contains two integers \(n\) and \(w\) where \(n\) is the number of boxes and \(w\) is the maximum weight allowed per container.
2. The second line contains \(n\) space-separated integers representing the weights of the boxes.

outputFormat

The output should be a single integer printed to standard output (stdout) which indicates the minimum number of containers required to load all the boxes without exceeding the weight limit in any container.

3 10
3 5 7

2