Nước Cộng hòa IOI, nơi JOI-kun sinh sống, nổi tiếng với một hồ nước lớn. Hôm nay có một sự kiện sưu tập dấu diễn ra quanh hồ.

Có \(N\) loại dấu đặt quanh hồ, đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ. Chu vi hồ là \(L\) mét. Loại dấu thứ \(i\) (\(1 \le i \le N\)) nằm cách điểm xuất phát \(X_i\) mét theo chiều kim đồng hồ.

Mỗi người tham gia bắt đầu tại điểm xuất phát. Sau khi sự kiện bắt đầu, họ có thể di chuyển quanh hồ theo cả chiều kim đồng hồ lẫn ngược chiều kim đồng hồ. Chỉ có thể thu thập loại dấu thứ \(i\) nếu đến vị trí của nó không muộn hơn \(T_i\) giây kể từ lúc bắt đầu, tức là đến đúng thời điểm \(T_i\) vẫn được.

JOI-kun tham gia sự kiện và mất \(1\) giây để đi \(1\) mét. Có thể bỏ qua thời gian dành cho mọi hoạt động khác.

Cho số loại dấu, chu vi hồ, vị trí và thời hạn thu thập của mỗi loại dấu, hãy tính số loại dấu nhiều nhất mà JOI-kun có thể thu thập.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

N L
X_1 ... X_N
T_1 ... T_N

Dữ liệu ra

In ra một dòng chứa số loại dấu nhiều nhất có thể thu thập.

Ràng buộc

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

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung. Chỉ nhận được điểm của một nhóm nếu vượt qua tất cả bộ dữ liệu trong nhóm đó.

1. \(5\) điểm: \(N \le 12\), \(L \le 200\) và \(T_i \le 200\) với mọi \(1 \le i \le N\)
2. \(10\) điểm: \(N \le 15\)
3. \(10\) điểm: \(L \le 200\) và \(T_i \le 200\) với mọi \(1 \le i \le N\)
4. \(75\) điểm: Không có

Ví dụ

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

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2019/2020 ngày 9 tháng 2 năm 2020. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.