Minimum Number of Containers

You are given n items, each with a certain weight, and an unlimited number of containers. Each container has a maximum weight capacity W. Your task is to determine the minimum number of containers required to pack all items such that the sum of weights in any container does not exceed W.

Formally, let the weights be given by \(w_1, w_2, \dots, w_n\). You need to partition these items into the minimum number of subsets such that for each subset \(S\), the condition \[ \sum_{i \in S} w_i \leq W \] holds.

A greedy algorithm that sorts the items in descending order and then packs them into containers one by one will work for the intended input sizes. Note that items cannot be split.

inputFormat

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

• The first line contains two integers n and W, where n (\(1 \le n \le 10^5\)) represents the number of items and W (\(1 \le W \le 10^9\)) is the maximum weight capacity of each container.
• The second line contains n space-separated integers representing the weights of the items.

It is guaranteed that each weight is a positive integer.

outputFormat

Output a single integer on stdout representing the minimum number of containers required to pack all the items.

5 10
2 3 5 7 1

2