CF1498B.Box Fitting

You are given $n$ rectangles, each of height $1$. Each rectangle's width is a power of $2$ (i. e. it can be represented as $2^x$ for some non-negative integer $x$).

You are also given a two-dimensional box of width $W$. Note that $W$ may or may not be a power of $2$. Moreover, $W$ is at least as large as the width of the largest rectangle.

You have to find the smallest height of this box, such that it is able to fit all the given rectangles. It is allowed to have some empty space left in this box after fitting all the rectangles.

You cannot rotate the given rectangles to make them fit into the box. Moreover, any two distinct rectangles must not overlap, i. e., any two distinct rectangles must have zero intersection area.

See notes for visual explanation of sample input.

给你 $n$ 个矩形，每个矩形的高度均为 $1$。每个矩形的宽度均为 $2$ 的幂（即可以表示为 $2^x$，其中 $x$ 为非负整数）。

你还给定一个二维盒子，其宽度为 $W$。注意：$W$ 可能不是 $2$ 的幂；此外，$W$ 不小于所有矩形中最大宽度。

你需要求出该盒子的最小高度，使得所有给定的矩形都能放入其中。允许盒子在放入所有矩形后仍留有空余空间。

不允许旋转给定的矩形以使其适配盒子。此外，任意两个不同的矩形不得重叠，即任意两个不同矩形的交集面积必须为零。

有关样例输入的图示说明，请参见“注释”部分。

The first line of input contains one integer $t$ ($1 \le t \le 5 \cdot 10^3$) — the number of test cases. Each test case consists of two lines.

For each test case:

• the first line contains two integers $n$ ($1 \le n \le 10^5$) and $W$ ($1 \le W \le 10^9$);
• the second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^6$), where $w_i$ is the width of the $i$-th rectangle. Each $w_i$ is a power of $2$;
• additionally, $\max\limits_{i=1}^{n} w_i \le W$.

The sum of $n$ over all test cases does not exceed $10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 5 \cdot 10^3$），表示测试用例的数量。每个测试用例由两行组成。

对于每个测试用例：

• 第一行包含两个整数 $n$（$1 \le n \le 10^5$）和 $W$（$1 \le W \le 10^9$）；
• 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 10^6$），其中 $w_i$ 表示第 $i$ 个矩形的宽度；每个 $w_i$ 均为 $2$ 的幂；
• 此外，满足 $\max\limits_{i=1}^{n} w_i \le W$。

所有测试用例中 $n$ 的总和不超过 $10^5$。

Output $t$ integers. The $i$-th integer should be equal to the answer to the $i$-th test case — the smallest height of the box.

输出 $t$ 个整数。第 $i$ 个整数应等于第 $i$ 个测试用例的答案——即盒子的最小高度。

For the first test case in the sample input, the following figure shows one way to fit the given five rectangles into the 2D box with minimum height:

In the figure above, the number inside each rectangle is its width. The width of the 2D box is $16$ (indicated with arrow below). The minimum height required for the 2D box in this case is $2$ (indicated on the left).

In the second test case, you can have a minimum height of three by keeping two blocks (one each of widths eight and two) on each of the three levels.

对于样例输入中的第一个测试用例，下图展示了一种将给定的五个矩形放入二维箱子中的方式，使得箱子高度最小：

在上图中，每个矩形内部的数字表示其宽度。二维箱子的宽度为 $16$（由下方箭头标出）。本例中，二维箱子所需的最小高度为 $2$（由左侧标出）。

在第二个测试用例中，可通过在每一层放置两个方块（每层各一个宽度为 $8$ 和一个宽度为 $2$ 的方块），实现最小高度 $3$。