← 返回题目列表

AtCoder · joi2020ho_c

C. 印章拉力赛 3(收集印章 3)

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

配点: 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).

小課題

  1. (5 点) N \leqq 12,L \leqq 200,T_i \leqq 200 (1 \leqq i \leqq N).
  2. (10 点) N \leqq 15.
  3. (10 点) L \leqq 200,T_i \leqq 200 (1 \leqq i \leqq N).
  4. (75 点)没有额外的限制。

入力例 1

6 25
3 4 7 17 21 23
11 7 17 10 8 10

出力例 1

4

如果您执行以下操作,JOI 将被 您可以获得 4 印章。

  1. 逆时针 2 向前移动米。自盖章集会开始以来经过的时间是 2 秒,所以印台 您可以用 6 来标记它。
  2. 进一步逆时针方向 2 向前移动米。自盖章集会开始以来经过的时间是 4 秒,所以印台 您可以用 5 来标记它。
  3. 顺时针 7 向前移动米。自盖章集会开始以来经过的时间是 11 秒,所以印台 您可以用 1 来标记它。
  4. 进一步顺时针方向 您不能用 1 向前移动米。自盖章集会开始以来经过的时间是 12 秒,所以印台 您可以用 2 盖章。
  5. 进一步顺时针方向 您不能用 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