Minimum Containers

You are given a set of products with their weights and a container with a maximum weight capacity. Your task is to determine the minimum number of containers required to hold all the products such that the sum of the weights in each container does not exceed the given capacity.

Input Format:

• The first line contains two integers n and maxCapacity, where n is the number of products and maxCapacity is the maximum allowed weight per container.
• The second line contains n integers representing the weights of the products.

Output Format:

• Output a single integer representing the minimum number of containers required.

Note: If there are no products (n = 0), output 0.

Algorithm Hint:

You might consider a greedy approach where you sort the products in descending order and then iterate over them to allocate each product to an existing container (if it fits) or start a new container if necessary. In mathematical terms, if we denote the sequence of product weights as \(w_1, w_2, \dots, w_n\) after sorting in descending order, and \(C\) as the set of containers with current loads, for each weight \(w_i\) assign it to some container \(c_j \in C\) so that \(\text{load}(c_j) + w_i \le maxCapacity\) or create a new container if such a container does not exist.

inputFormat

The input is read from stdin and consists of two lines:

• First line: Two space-separated integers n (the number of products) and maxCapacity (the maximum capacity of each container).
• Second line: n space-separated integers representing the weights of the products.

outputFormat

Output the minimum number of containers required as a single integer to stdout.

## sample

5 10
3 6 2 8 7

3