#5916
서브태스크

채점 보류

Collecting Stamps 3 2초 512MB

문제

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 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 ≤ i ≤ 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.

입력

Read the following data from the standard input. Given values are all integers.

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

[제한]

1 ≤ N ≤ 200.
2 ≤ L ≤ 1 000 000 000.
1 ≤ X_i < L (1 ≤ i ≤ N).
X_i < X_i+1 (1 ≤ i ≤ N − 1).
0 ≤ T_i ≤ 1 000 000 000 (1 ≤ i ≤ N).

출력

Write the answer in one line to the standard output.

부분문제

번호	점수	조건
#1	5점	N ≤ 12, L ≤ 200, T_i ≤ 200 (1 ≤ i ≤ N).
#2	10점	N ≤ 15.
#3	10점	L ≤ 200, T_i ≤ 200 (1 ≤ i ≤ N).
#4	75점	No additional constraints.

예제1

입력

6space_bar25keyboard_return
3space_bar4space_bar7space_bar17space_bar21space_bar23keyboard_return
11space_bar7space_bar17space_bar10space_bar8space_bar10

출력

JOI-kun can collect 4 types of stamps as described below:

Walk 2 meters counter-clockwise. He can collect the 6th stamp as it is 2 minutes since the rally starts.
Walk 2 meters counter-clockwise. He can collect the 5th stamp as it is 4 minutes since the rally starts.
Walk 7 meters clockwise. He can collect the 1st stamp as it is 11 minutes since the rally starts.
Walk 1 meter clockwise. He cannot collect the 2nd stamp as it is 12 minutes since the rally starts.
Walk 3 meters clockwise. He can collect the 3rd stamp as it is 15 minutes since the rally starts.

It is impossible for JOI-kun to collect 5 or more stamps, so the answer is 4

예제2

입력

5space_bar20keyboard_return
4space_bar5space_bar8space_bar13space_bar17keyboard_return
18space_bar23space_bar15space_bar7space_bar10

출력

JOI-kun can collect all the stamps by walking around the lake counter-clockwise.

예제3

입력

4space_bar19keyboard_return
3space_bar7space_bar12space_bar14keyboard_return
2space_bar0space_bar5space_bar4

출력

Unfortunately, JOI-kun cannot collect any stamps, no matter how he moves.

예제4

입력

10space_bar87keyboard_return
9space_bar23space_bar33space_bar38space_bar42space_bar44space_bar45space_bar62space_bar67space_bar78keyboard_return
15space_bar91space_bar7space_bar27space_bar31space_bar53space_bar12space_bar91space_bar89space_bar46

출력

출처

JOI 2020

#5916 upload -회 done -회 how_to_reg -명 call_split 서브태스크 stop_circle 채점 보류

Collecting Stamps 3 timer 2초 memory 512MB

문제 picture_in_picture_alt text_fields

입력

출력

부분문제

예제1

예제2

예제3

예제4

출처

역링크

#5916
서브태스크

채점 보류

Collecting Stamps 3 2초 512MB

문제