Minimum Number of Crates

You are given a list of product weights and a maximum capacity for a crate. Your task is to determine the minimum number of crates required to pack all the products such that the total weight in each crate does not exceed the maximum capacity.

The problem can be stated as follows:

Given an integer N representing the number of products, an integer W representing the maximum crate capacity, and a list of N integers where each integer represents the weight of a product, find the minimum number of crates needed to store all the products. Each crate can hold products as long as their total weight is at most W.

Note: If there are no products (N = 0), the output should be 0.

Hint: One approach is to sort the weights in non-increasing order and attempt to place each weight into the first crate in which it fits (first-fit decreasing strategy). This greedy strategy works well for the problem instances provided.

The capacity constraint in mathematical form is: $$\sum_{i \in S} w_i \leq W$$ for each crate, where \(S\) is the set of products in a crate and \(w_i\) is the weight of the product.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers separated by a space: N (the number of products) and W (the maximum capacity of each crate).
• If N > 0, the second line contains N space-separated integers representing the weights of the products.

If N is 0, no weights are provided.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of crates required.

## sample

1 10
5

1