Minimum Boat Trips

You are given a boat that can carry at most two travelers at a time with a combined weight not exceeding a given limit (W). Given (N) travelers with known weights, determine the minimum number of trips required to ferry all travelers across the river.

Two travelers can share a trip if and only if (w_i + w_j \leq W), where (w_i) and (w_j) are the weights of the travelers. Use a greedy strategy with sorting and two pointers to solve this problem efficiently.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T), the number of test cases. For each test case, the first line contains two integers (N) and (W) where (N) is the number of travelers and (W) is the maximum weight capacity of the boat. The next line contains (N) space-separated integers representing the weights of the travelers.

outputFormat

For each test case, print a single line containing the minimum number of trips required to ferry all travelers across the river, written to standard output (stdout).## sample

4
5 200
90 50 70 30 100
3 100
40 50 60
6 300
150 120 180 30 50 60
1 200
150

3
2
3
1