Problem Description

JOI-kun lives in the IOI country, which is famous for its large lake. Today, a stamp rally event will be held around the lake.

Around the lake, $ N $ stamp stands are installed, numbered from $ 1 $ to $ N $ in a clockwise manner. The circumference of the lake is $ L $ meters, and the stamp stand $ i $ ($1 \leq i \leq N$) is located $ X_i $ meters away from the starting point along the lake's circumference in a clockwise direction.

Each participant of the stamp rally starts at the starting point at the beginning of the event and can move either clockwise or counterclockwise along the lake's circumference. Participants can stamp only when they arrive at a stamp stand that they have not stamped at before. However, the stamp stand $ i $ ($1 \leq i \leq N$) will be removed after $ T_i $ seconds have passed since the start of the rally, and participants cannot stamp there after that. Note that if a participant arrives exactly at $ T_i $ seconds, they can still stamp.

JOI-kun is a participant in this stamp rally. It takes him $ 1 $ second to travel $ 1 $ meter, and since he is skilled at stamping, the time it takes to stamp is negligible.

Given the number of stamp stands, the circumference of the lake, the locations of each stamp stand, and the removal times of each stamp stand, write a program to determine the maximum number of stamps JOI-kun can collect.

Input Format

The input is given from the standard input in the following format. All values are integers.

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

Output Format

Output the maximum number of stamps JOI-kun can collect on a single line to the standard output.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4

Sample Input #2

5 20
4 5 8 13 17
18 23 15 7 10

Sample Output #2

5

Sample Input #3

4 19
3 7 12 14
2 0 5 4

Sample Output #3

0

Sample Input #4

10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46

Sample Output #4

5

Notes/Hints

Constraints

• $1 \leq N \leq 200$.
• $2 \leq L \leq 1\,000\,000\,000$.
• $1 \leq X_i < L$ ($1 \leq i \leq N$).
• $ X_i < X_{i+1} $ ($1 \leq i \leq N - 1$).
• $0 \leq T_i \leq 1\,000\,000\,000$ ($1 \leq i \leq N$).

Subtasks

1. ($ 5 $ points) $N \leq 12$, $L \leq 200$, $T_i \leq 200$ ($1 \leq i \leq N$).
2. ($ 10 $ points) $N \leq 15$.
3. ($ 10 $ points) $L \leq 200$, $T_i \leq 200$ ($1 \leq i \leq N$).
4. ($ 75 $ points) No additional constraints.

Sample Explanation 1

JOI-kun can collect $ 4 $ stamps by doing the following:
1. Move $ 2 $ meters counterclockwise. The elapsed time is $ 2 $ seconds, so he can stamp at stand $ 6 $.
2. Move another $ 2 $ meters counterclockwise. The elapsed time is $ 4 $ seconds, so he can stamp at stand $ 5 $.
3. Move $ 7 $ meters clockwise. The elapsed time is $ 11 $ seconds, so he can stamp at stand $ 1 $.
4. Move another $ 1 $ meter clockwise. The elapsed time is $ 12 $ seconds, so he cannot stamp at stand $ 2 $.
5. Move another $ 3 $ meters clockwise. The elapsed time is $ 15 $ seconds, so he can stamp at stand $ 3 $.
No matter how he moves, JOI-kun cannot collect more than $ 4 $ stamps, so output $ 4 $.

Sample Explanation 2

JOI-kun can collect all stamps by continuously moving counterclockwise around the lake after the start of the rally.

Sample Explanation 3

Unfortunately, no matter how JOI-kun moves, he cannot collect any stamps.

见题面 Input 部分

见题面 Output 部分