우표 수집 3

시간 제한2초메모리 제한512 MB

요약

원형 호수를 따라 놓인 N개의 스탬프에 각각 수집 기한이 주어질 때, 출발점에서 시작해 모을 수 있는 스탬프 종류의 최댓값을 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 구간, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

JOI군이 사는 IOI 공화국은 큰 호수로 유명하다. 오늘 호수 주변에서 우표 랠리 행사가 열린다.

호수 주변에는 N종류의 우표가 있다. 이 우표들은 시계 방향으로 1번부터 N번까지 번호가 붙어 있다. 호수의 둘레는 L이고, i번 우표(1 ≤ i ≤ N)는 랠리 시작 지점에서 시계 방향으로 Xi미터 떨어진 곳에 있다.

참가자는 모두 랠리 시작 지점에 서 있다. 랠리가 시작된 후 참가자는 시계 방향과 반시계 방향 모두로 호수 주변을 이동할 수 있다. 참가자는 랠리 시작 시각부터 Ti초 이내(경계 포함)에 i번 우표가 있는 곳에 도착한 경우에만 i번 우표(1 ≤ i ≤ N)를 수집할 수 있다.

JOI군은 랠리 참가자이다. 그는 1미터를 이동하는 데 1초가 걸린다. 그가 걸리는 다른 모든 시간은 무시할 수 있다.

우표 종류의 수, 호수의 둘레, 각 우표의 위치, 그리고 JOI군이 각 우표를 수집할 수 있는 시각이 주어질 때, 그가 수집할 수 있는 우표 종류의 최대 개수를 계산하는 프로그램을 작성하라.

입력

표준 입력에서 다음 데이터를 읽는다. 주어지는 값은 모두 정수이다.

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

출력

답을 한 줄로 표준 출력에 쓴다.

제한

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).

예제4

예제 1
입력
```
6 25
3 4 7 17 21 23
11 7 17 10 8 10
```
예상 출력
```
4
```
예제 2
입력
```
5 20
4 5 8 13 17
18 23 15 7 10
```
예상 출력
```
5
```
예제 3
입력
```
4 19
3 7 12 14
2 0 5 4
```
예상 출력
```
0
```

예제 4

입력

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

예상 출력