您在热门平台 YooCube 上的观看列表中有 $$$n$$$ 个视频。第 $$$i$$$ 个视频持续 $$$d_i$$$ 分钟。
YooCube 最近增加了广告的频率。广告仅在视频之间展示。视频播放完毕后,如果满足以下两个条件之一,则会显示广告:
- 自上次广告以来已观看了三个视频;
- 自上一个广告结束以来至少已过去 $$$k$$$ 分钟。
您想要观看观看列表中的 $$$n$$$ 视频。假设您刚刚观看了一个广告,并且您可以选择 $$$n$$$ 视频的顺序,那么您必须观看的最少广告数量是多少?您可以在上一个视频或广告结束后立即开始播放新视频,结束后无需观看任何广告。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100\,000$$$) — 测试用例的数量。 $$$t$$$ 测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 100\,000, 1 \leq k \leq 30\,000$$$) — 观看列表中的视频数量以及确定何时展示广告的参数。
第二行包含 $$$n$$$ 整数 $$$d_1, d_2, \ldots, d_n (1 \leq d_i \leq 10\,000)$$$ — 视频的长度。
所有测试用例的 $$$n$$$ 值的总和不超过 $$$10^6$$$。
输出
对于每个测试用例,打印您需要观看的最少广告数量。
示例
输入复制
58 254 5 18 3 17 17 18 147 2120 14 1 4 20 8 48 120 5 9 4 14 12 2 208 372 13 13 11 12 19 16 184 3815 3 14 7
输出复制
2 2 7 2 1
注意
在 第一个测试用例,可能的观看顺序是 $$$4, 1, 8, 2, 5, 6, 7, 3$$$ (相应的长度是 $$$3, 4, 14, 5, 17, 17, 18, 18$$$)。按照此顺序,您必须在前三个视频之后观看广告,然后在后三个视频之后观看另一个广告。请注意,看完所有视频后,您不必再观看广告。