配点: 100 点
JOI 您居住的 IOI 国家以其大湖而闻名。今天,湖边将举行集章比赛。
环湖 N 印台已安装,顺时针方向。 它们的编号最大为 1 减去 N 。湖的周长是 L 米和印台 i (1 \leqq i \leqq N) 从盖章拉力赛起点顺时针绕湖行驶。 X_i 安装在前方 1 米处。
盖章拉力赛开始时,每个盖章拉力赛的参与者都处于起点,并且在盖章拉力赛开始后可以顺时针或逆时针绕湖移动。当参与者到达安装印台的地点时,如果他们尚未在该印台上盖章,则只能盖章。 只能按 1 次。然而,印台 i (1 \leqq i \leqq N) 从盖章拉力赛开始 T_i 几秒钟后它将被删除,即使参与者在该时间之后到达,他们也将无法再在该盖章摊上盖章。此外, 如果参与者正好在T_i 秒内到达,他们就可以被盖章。
JOI 您是本次集章比赛的参与者。和你打交道 1 前往里程表 需要 1 秒。而且,由于JOI擅长盖章,所以盖章所需的时间可以忽略不计。
给定印章架的数量、湖的周长、每个印章架安装的位置以及每个印章架被拆除的时间,编写一个程序来找出 JOI 可以盖印的最大印章数量。
入力
输入是按以下格式从标准输入给出的。所有输入值都是整数。
N L X_1 \cdots X_N T_1 \cdots T_N
出力
JOI 您可以按下的最大印记数量将输出到标准输出。 1 逐行输出。
制約
- 1 \leqq N \leqq 200.
- 2 \leqq L \leqq 1\,000\,000\,000.
- 1 \leqq X_i < L (1 \leqq i \leqq N).
- X_i < X_{i+1} (1 \leqq i \leqq N - 1).
- 0 \leqq T_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
小課題
- (5 点) N \leqq 12,L \leqq 200,T_i \leqq 200 (1 \leqq i \leqq N).
- (10 点) N \leqq 15.
- (10 点) L \leqq 200,T_i \leqq 200 (1 \leqq i \leqq N).
- (75 点)没有额外的限制。
入力例 1
6 25 3 4 7 17 21 23 11 7 17 10 8 10
出力例 1
4
如果您执行以下操作,JOI 将被 您可以获得 4 印章。
- 逆时针 2 向前移动米。自盖章集会开始以来经过的时间是 2 秒,所以印台 您可以用 6 来标记它。
- 进一步逆时针方向 2 向前移动米。自盖章集会开始以来经过的时间是 4 秒,所以印台 您可以用 5 来标记它。
- 顺时针 7 向前移动米。自盖章集会开始以来经过的时间是 11 秒,所以印台 您可以用 1 来标记它。
- 进一步顺时针方向 您不能用 1 向前移动米。自盖章集会开始以来经过的时间是 12 秒,所以印台 您可以用 2 盖章。
- 进一步顺时针方向 您不能用 3 向前移动米。自盖章集会开始以来经过的时间是 15 秒,所以印台 您可以用 3 来标记它。
无论怎么动,JOI 您不能粘贴超过 5 的邮票,所以 输出4 。 你只需要砍掉
入力例 2
5 20 4 5 8 13 17 18 23 15 7 10
出力例 2
5
JOI 盖章拉力赛开始后,继续绕湖逆时针移动即可在所有盖章站盖章。
入力例 3
4 19 3 7 12 14 2 0 5 4
出力例 3
0
不幸的是,无论你如何移动,JOI都无法贴上印记。
入力例 4
10 87 9 23 33 38 42 44 45 62 67 78 15 91 7 27 31 53 12 91 89 46
出力例 4
5