Collecting Stamps 3

Time limit2sMemory limit512 MB

Summary

On a circular lake, N stamps sit at given positions with individual collection deadlines; find the maximum number of stamps JOI-kun can collect starting from position 0.

Level: Hard8 of 10
Topics: Dynamic programming, Intervals, Greedy, Implementation
Solved: No attempts yet

Problem

The Republic of IOI, where JOI-kun lives, is famous for a large lake. Today, a stamp rally event takes place around the lake.

There are N types of stamps situated around the lake. These stamps are numbered from 1 to N, in clockwise order. The perimeter of the lake is L, and the i-th stamp (1 ≤ i ≤ N) is located at Xi meters clockwise from the starting point of the stamp rally.

Every participant stands at the starting point of the rally. After the rally starts, each participant can move around the lake, both clockwise and counter-clockwise. A participant can collect the i-th stamp (1 ≤ i ≤ N) only if they arrive at the location of the i-th stamp within Ti seconds (inclusive) since the rally starts.

JOI-kun is a participant of the stamp rally. He takes 1 second to move 1 meter. All other times he takes can be ignored.

Write a program that, given the number of types of stamps, the perimeter of the lake, the location of each stamp, and the time until which JOI-kun can collect each stamp, calculates the maximum number of types of stamps he can collect in total.

Input

Read the following data from the standard input. All given values are integers.

N L
X1 . . . XN
T1 . . . TN

Output

Write the answer in one line to the standard output.

Constraints

1 ≤ N ≤ 200.
2 ≤ L ≤ 1 000 000 000.
1 ≤ Xi < L (1 ≤ i ≤ N).
Xi < Xi+1 (1 ≤ i ≤ N − 1).
0 ≤ Ti ≤ 1 000 000 000 (1 ≤ i ≤ N).

Examples4

Example 1
Input
```
6 25
3 4 7 17 21 23
11 7 17 10 8 10
```
Expected output
```
4
```
Example 2
Input
```
5 20
4 5 8 13 17
18 23 15 7 10
```
Expected output
```
5
```
Example 3
Input
```
4 19
3 7 12 14
2 0 5 4
```
Expected output
```
0
```

Example 4

Input

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

Expected output