JOI '19 Final P3 - Collecting Stamps 3

View as PDF

Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 512M

Problem type

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 \le i \le N) is located at X_i meters clockwise from the starting point of the stamp rally.

Each participant stands at the starting point of the stamp rally. After the rally starts, each participant can move around the lake, both clockwise and counter-clockwise. Each participant can collect the i-th stamp (1 \le i \le N) only if they arrive at where the i-th stamp is located within T_i seconds (inclusive) since the rally starts.

JOI-kun is a participant of the stamp rally. He takes 1 second to move 1 meter. You can ignore all the other times which he takes.

Write a program that, given the number of types of stamps, the perimeter of the lake, where each stamp is located, 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 Specification

The first line contains two space separated integers N and L (1 \le N \le 200, 2 \le L \le 10^9).

The second line contains N integers, X_i (1 \le X_i < L and X_i < X_{i+1}).

The third line contains N integers, T_i (0 \le T_i \le 10^9).

Output Specification

Write the answer in one line to the standard output.

Sample Input 1

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

Sample Output 1


Sample Input 2

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

Sample Output 2



There are no comments at the moment.