给你 $$$n$$$ 个矩形,每个矩形的高度为 $$$1$$$。每个矩形的宽度是 $$$2$$$ 的幂(即,对于某些非负整数 $$$x$$$,它可以表示为 $$$2^x$$$)。
您还会获得一个宽度为 $$$W$$$ 的二维框。请注意,$$$W$$$ 可能是也可能不是 $$$2$$$ 的幂。此外,$$$W$$$ 至少与最大矩形的宽度一样大。
你必须找到这个盒子的最小高度,以便它能够适合所有给定的矩形。拟合完所有矩形后,该框中允许留有一些空白。
您无法旋转给定的矩形以使其适合框。此外,任何两个不同的矩形不得重叠,即。即,任何两个不同的矩形的交叉面积必须为零。
请参阅注释以了解示例输入的直观说明。
输入
输入的第一行包含一个整数 $$$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$$$。
输出
输出 $$$t$$$ 整数。第 $$$i$$$ 个整数应该等于第 $$$i$$$ 个测试用例的答案 - 盒子的最小高度。
示例
输入 #1
2 5 16 1 2 8 4 8 6 10 2 8 8 2 2 8
输出 #1
2 3
注意
对于示例输入中的第一个测试用例,下图显示了将给定的五个矩形装入具有最小高度的 2D 框的一种方法:
上图中,每个矩形内部的数字就是其宽度。 2D 框的宽度为 $$$16$$$(用下面的箭头表示)。在这种情况下,2D 框所需的最小高度为 $$$2$$$(如左侧所示)。
在第二个测试用例中,通过在三个级别中的每一层上保留两个块(宽度为 8 和 2 各一个),可以使最小高度为 3。