Minimum Number of Containers

The problem is to determine the minimum number of containers required to store a set of items when each container has a maximum weight capacity. You are given several test cases; each test case contains the number of items, the capacity of the container, and the list of item weights. You need to place the items into containers so that the sum of the weights in any container does not exceed the capacity, while minimizing the total number of containers used.

The problem can be modeled as a bin packing problem. A common heuristic to approach this is the First-Fit Decreasing strategy, where the items are sorted in descending order and then each item is placed in the first container that can accommodate it. Formally, if we denote the weight of an item by (w_i) and the container capacity by (W), then for each test case, you must find the minimum number (k) such that there exists a partition of the items into (k) subsets where for each subset (S_j), the inequality (\sum_{w_i \in S_j} w_i \leq W) holds.

inputFormat

The first line contains an integer (T) representing the number of test cases. Each test case consists of two lines:

• The first line contains two integers \(n\) and \(W\): the number of items and the maximum weight capacity of a container.
• The second line contains \(n\) space-separated integers, the weights of the items.

outputFormat

For each test case, output a single line with one integer — the minimum number of containers required.## sample

2
5 10
5 7 3 9 2
4 15
8 4 10 5

3
2