Problem Description

Given a circle with a circumference of $L$ meters, starting from a point, there are $N$ Tickle-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 Tickle-Bear statue within $T_i$ seconds, it will emit a "Woohoohoo" sound and explode.

JOI-kun is at this starting point, and he can move one meter per second, either clockwise or counterclockwise.

JOI-kun wants to know the maximum number of Tickle-Bear statues he can collect.

Input Format

The first line contains two integers $N$ and $L$, representing the number of statues and the circumference of the circle, respectively.
The second line contains $N$ integers $X_i$, representing the positions of each statue in meters clockwise from the starting point.
The third line contains $N$ integers $T_i$, representing the time limits in seconds for collecting each statue.

Output Format

Output a single integer representing the answer.

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

Sample 1 Explanation

JOI-kun can collect 4 Tickle-Bear statues using the following strategy:

Sample 2 Explanation

JOI-kun can simply move counterclockwise continuously.

Sample 3 Explanation

JOI-kun cannot collect any statues.

Data Constraints

This problem is group-tested.
- 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 additional constraints.

For $100\%$ of the data:

• $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.

见题面 Input 部分

见题面 Output 部分