Minimum Number of Trips to Deliver Provisions

You are given a number of castles and a supply wagon with a maximum load capacity. Each castle requires a certain amount of provisions. Your task is to determine the minimum number of trips needed to deliver all the provisions to the castles.


Formally, you are given an integer $N$ representing the number of castles, an array $a = [a_1,a_2,...,a_N]$ where $a_i$ is the amount of provisions required by the $i$-th castle, and an integer $W$ representing the maximum capacity of the wagon. In each trip, you can deliver a subset of provisions such that the total does not exceed $W$. You need to minimize the number of trips required to deliver all provisions.

Note: The solution uses a greedy strategy by sorting the provisions in descending order and then trying to fill each trip as much as possible.

inputFormat

The input is given via standard input (stdin).

The first line contains two integers $N$ and $W$ separated by a space, where $N$ is the number of castles and $W$ is the maximum capacity of the wagon.

The second line contains $N$ integers separated by spaces, representing the provisions required by each castle.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of trips required to deliver all the provisions.## sample

5 8
2 3 7 4 1

3