#216011. [JOI Final 2026] 面包师 / Baker

本题测试数据较大，可能需要等待较长时间加载数据。

JOI 面包店是一家以令人垂涎的牛角面包而闻名的面包店。JOI 面包店有 名面包师，编号从 到 。面包师 () 制作一个牛角面包需要 分钟。一名面包师不能同时制作多个牛角面包。

今天，有 名编号从 到 的顾客计划光顾 JOI 面包店，每位顾客都计划订购一个牛角面包。顾客 () 将在时间 订购一个牛角面包，其中时间 表示从现在起 分钟后的时间。然而，如果顾客在下单后 分钟内无法收到他们的牛角面包，他们就会放弃并离开商店。换句话说，为了完成顾客 () 的订单，牛角面包必须在时间 之前（包括恰好在时间 ）制作完成。

管理 JOI 面包店的经理 K 计划今天只让一名面包师工作，并且正在考虑派遣哪位面包师以及在什么时间开始工作。由于面包师在值班期间会高度专注地制作面包，他们会忽略所有在他们开始时间之后（不包括恰好在开始时间）下的订单。也就是说，在时间 开始工作的面包师无法完成满足 的顾客 () 的订单。

经理 K 目前正在考虑 个工作计划。第 个计划 () 是让面包师 在时间 开始工作。为了帮助做出决定，对于这 个计划中的每一个，他想知道如果执行该计划，可以完成的订单的最大顾客数量。请注意，面包师到达后开始制作牛角面包所需的时间，以及制作完一个后开始制作下一个新牛角面包所需的时间，均可以忽略不计。

给定有关光顾 JOI 面包店的顾客信息和工作计划，编写一个程序，求出每个计划中可以完成订单的最大顾客数量。

从标准输入读取以下数据。

向标准输出写入 行。输出的第 行 () 应包含一个整数，表示在第 个工作计划中可以完成订单的最大顾客数量。

样例输入 1

4 4 6 4
0 2 3 8
2 3
1 6
3 3
4 7

样例输出 1

3
2
2
0

样例输入 2

20 5 12 4
1 2 4 8 10
1 12
3 10
3 11
15 10

样例输出 2

5
4
3
0

样例输入 3

100000 6 272273 10
5 9 209 8128 17202 50102
164 9
11 24
835 9267
2 256
2 314156
18475 142
1826 18978
44757 1
4 1646
218 44

样例输出 3

2
2
4
3
1
2
5
0
3
2

样例 1

关于第 个工作计划，面包师 在时间 开始工作，可以完成 位顾客 和 的订单，例如方案如下：

• 首先，为了完成顾客 的订单，在时间 开始制作牛角面包，并在 分钟后的时间 完成。（这满足了在时间 之前完成的条件。）
• 接下来，为了完成顾客 的订单，在时间 开始制作牛角面包，并在 分钟后的时间 完成。（这满足了在时间 之前完成的条件。）
• 最后，为了完成顾客 的订单，在时间 开始制作牛角面包，并在 分钟后的时间 完成。（这满足了在时间 之前完成的条件。）

顾客 的订单被忽略，因为它是在面包师开始时间之后到达的，所以无法完成。因此，最多可以完成 位顾客的订单，所以第 行输出 。

关于第 个工作计划，面包师 在时间 开始工作，可以完成 位顾客 和 的订单，例如方案如下：

• 首先，为了完成顾客 的订单，在时间 开始制作牛角面包，并在 分钟后的时间 完成。（这满足了在时间 之前完成的条件。）
• 接下来，为了完成顾客 的订单，在时间 开始制作牛角面包，并在 分钟后的时间 完成。（这满足了在时间 之前完成的条件。）

顾客 的订单由于在开始时间之后到达而被忽略。此外，顾客 的订单由于需要在时间 之前完成，因此无法完成。因此，最多可以完成 位顾客的订单，所以第 行输出 。

关于第 个工作计划，面包师 在时间 开始工作，可以完成顾客 和 、或者顾客 和 的订单，但不能同时完成顾客 和 的所有订单。他们也无法完成在开始时间之后到达的顾客 的订单。因此，最多可以完成 位顾客的订单，所以第 行输出 。

关于第 个工作计划，面包师 在时间 开始工作，无法完成任何顾客的订单。因此，第 行输出 。

该样例输入满足子任务 和 的约束。

样例 2

该样例输入满足所有子任务的约束。

样例 3

该样例输入满足子任务 和 的约束。

约束条件

• 。
• 。
• 。
• 。
• ()。
• ()。
• ()。
• ()。
• 给定的值均为整数。

子任务

1. (8 分) 。
2. (12 分) 。
3. (30 分) ()。
4. (10 分) ()。
5. (22 分) 。
6. (18 分) 无附加约束。