Problem Description

Given a circle with circumference $L$, starting from a point, there are $N$ black-and-white bear statues numbered from $1$ to $N$. The $i$-th statue is located $X_i$ meters clockwise from the starting point. If you do not collect this black-and-white bear statue within $T_i$ seconds, it will make a “wuppuppuppu” sound and then explode.

Now JOI-kun is at the starting point. He can move $1$ meter per second, and he may move either clockwise or counterclockwise.

JOI-kun wants to know: what is the maximum number of black-and-white bear statues he can collect?

Input Format

The first line contains two integers $N, L$, representing the number of statues and the circumference of the circle.
The second line contains $N$ integers $X_i$, representing how many meters clockwise each statue is located from the starting point.
The third line contains $N$ integers $T_i$, representing within how many seconds each statue must be collected.

Output Format

Output one integer on a single line, representing the answer.

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

4

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

5

4 19
3 7 12 14
2 0 5 4

0

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

5

Hint

Explanation for Sample 1

JOI-kun can collect $4$ black-and-white bear statues using the following strategy:

Explanation for Sample 2

JOI-kun can just keep walking counterclockwise.

Explanation for Sample 3

JOI-kun cannot obtain any statue.

Constraints

This problem uses bundled testdata.

• Subtask 1 (5 pts): $N \le 12$, $L \le 200$, $X_i \le 200$.
• Subtask 2 (10 pts): $N \le 15$.
• Subtask 3 (10 pts): $L \le 200$, $T_i \le 200$.
• Subtask 4 (75 pts): No special restrictions.

For $100\%$ of the testdata:

• $1 \le N \le 200$.
• $2 \le L \le 10^9$.
• $1 \le X_i < L$.
• $X_i < X_{i+1}$.
• $0 \le T_i \le 10^9$.

Notes

Translated from The 19th Japanese Olympiad in Informatics, Final Round C Stamp Rally 3.

Translated by ChatGPT 5