Alessandro is a big fan of TV series and is eager to discuss them with his friends. In the next days, they will be talking about different series, numbered from to , with series being discussed from day to day included. Note that time passes fast when having fun, thus in a single day they will discuss at most one series.
Alessandro has not watched any of those series yet, but he wants to talk with his friends as much as possible. However he only has a limited amount of free time and knows it will take him days to watch series . Alessandro can watch the series in any order and skip some, but he cannot start watching a new series before finishing the previous one. In order to take part in the discussion on day , Alessandro must have watched completely the tv series which is being talked about by the end of day .
For how many days, at most, can he take part in the discussion with his friends?
Input data
The input file consists of:
- a line containing integers : the number of TV series that will be discussed and the number of days.
- a line containing the integers .
- a line containing the integers .
- a line containing the integers .
Output data
The output file must contain a single line consisting of integer , the maximum number of days in which Alessandro can discuss TV series with his friends.
Constraints and clarifications
- .
- .
- for each .
- for each .
# | Points | Constraints |
---|---|---|
1 | 0 | Examples |
2 | 18 | |
3 | 25 | |
4 | 57 | No additional limitations |
Your program will be tested against several test cases grouped in subtasks. In order to obtain the score of a subtask, your program needs to correctly solve all of its test cases.
Example 1
stdin
2 4
2 4
2 4
1 2
stdout
2
Explanation
In the first sample case there are TV series and days.
- Series will be discussed on day and takes day to watch.
- Series will be discussed on days and and takes days to watch.
It is optimal for Alessandro to watch series on day and discuss it on day , then watch series on days and and discuss it on day . This will let Alessandro take part in both days of discussion.
Example 2
stdin
4 10
2 3 7 8
2 6 7 10
1 4 3 2
stdout
5
Explanation
In the second sample case there are TV series and days.
- Series will be discussed on day and takes day to watch.
- Series will be discussed on days and and takes days to watch.
- Series will be discussed on day and takes days to watch.
- Series will be discussed on days and and takes days to watch.
It is optimal for Alessandro to watch series on days and , and discuss it on days and and to watch series on days and , then discuss it on days and . This will let Alessandro participate to the discussion on days, and it can be proven that he cannot do better.