← 返回题目列表

Codeforces · 2068/C

C. 广告

中文机器翻译题面 查看原题

您在热门平台 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$$$。

输出

对于每个测试用例,打印您需要观看的最少广告数量。

示例

输入
复制

5
8 25
4 5 18 3 17 17 18 14
7 21
20 14 1 4 20 8 4
8 1
20 5 9 4 14 12 2 20
8 37
2 13 13 11 12 19 16 18
4 38
15 3 14 7

输出
复制

2
2
7
2
1

注意

在 第一个测试用例,可能的观看顺序是 $$$4, 1, 8, 2, 5, 6, 7, 3$$$ (相应的长度是 $$$3, 4, 14, 5, 17, 17, 18, 18$$$)。按照此顺序,您必须在前三个视频之后观看广告,然后在后三个视频之后观看另一个广告。请注意,看完所有视频后,您不必再观看广告。