Minimum Number of Trucks

You are given a set of packages, each with a specific weight, and trucks with a fixed carrying capacity ( C ). Your task is to determine the minimum number of trucks required to transport all the packages.

For each test case, you will receive two numbers ( n ) and ( C ), where ( n ) indicates the number of packages and ( C ) is the maximum total weight each truck can carry. This problem resembles the classic bin packing problem. A greedy strategy is applied: first, the package weights are sorted in descending order, and then repeatedly, packages are loaded into a truck until no additional package can fit without exceeding the capacity ( C ). The process repeats until all packages are assigned to trucks.

Note: All formulas are written in ( \LaTeX ) format. Example: The truck capacity condition can be expressed as ( \text{current load} + w_i \leq C ).

inputFormat

The input begins with an integer ( t ) ( (1 \leq t \leq 50) ), which denotes the number of test cases.

For each test case, the first line contains two integers ( n ) and ( C ), where ( n ) ( (1 \leq n \leq 1000) ) is the number of packages and ( C ) ( (1 \leq C \leq 10^9) ) is the capacity of each truck. The next line contains ( n ) space-separated integers ( w_1, w_2, \dots, w_n ) representing the weights of the packages.

outputFormat

For each test case, output a single line containing one integer — the minimum number of trucks required to transport all the packages.## sample

1
1 100
50

1