JOI 君的印章拉力赛问题

题目描述

JOI 君所居住的 IOI 国以拥有一个大湖而著名。今天，湖周围将举行一场印章拉力赛。

湖周围共设有 $N$ 个印章台，按顺时针方向编号从 $1$ 到 $N$。湖周长为 $L$ 米，印章台 $i$ ($1 \leqq i \leqq N$) 设在距离拉力赛起点顺时针方向前进 $X_i$ 米处。

拉力赛的参与者在开始时位于起点，并可以顺时针或逆时针沿湖周围移动。当参与者到达设有印章台的位置时，只有当他们尚未在该印章台上盖章时，才能在该印章台上盖章。然而，印章台 $i$ ($1 \leqq i \leqq N$) 将在拉力赛开始后 $T_i$ 秒被移除，并且此后参与者无法在该印章台上盖章。若参与者恰好在第 $T_i$ 秒到达该印章台，则仍可以盖章。

JOI 君是这场印章拉力赛的参与者。JOI 君每前进 $1$ 米需要 $1$ 秒。此外，JOI 君在盖章方面技艺娴熟，可以忽略盖章所需时间。

给定印章台数量、湖周长、各印章台位置和其移除时间，编写程序求出 JOI 君可以盖章的最大数量。

---

输入

输入从标准输入读取。输入值都是整数。

$N$ $L$ $X_1$ $\cdots$ $X_N$ $T_1$ $\cdots$ $T_N$

输出

将 JOI 君可以盖章的最大数量输出到标准输出。

---

约束条件

• $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 君可以按照以下方式盖章：

1. 逆时针前进 $2$ 米。此时距离拉力赛开始已经过去 $2$ 秒，因此 JOI 君可以在印章台 $6$ 上盖章。
2. 再逆时针前进 $2$ 米。此时距离拉力赛开始已经过去 $4$ 秒，因此 JOI 君可以在印章台 $5$ 上盖章。
3. 顺时针前进 $7$ 米。此时距离拉力赛开始已经过去 $11$ 秒，因此 JOI 君可以在印章台 $1$ 上盖章。
4. 再顺时针前进 $1$ 米。此时距离拉力赛开始已经过去 $12$ 秒，但此时 JOI 君不能在印章台 $2$ 上盖章。
5. 再顺时针前进 $3$ 米。此时距离拉力赛开始已经过去 $15$ 秒，因此 JOI 君可以在印章台 $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