TV Series

Alessandro is a big fan of TV series and is eager to discuss them with his friends. In the next $D$ days, they will be talking about $N$ different series, numbered from $0$ to $N − 1$, with series $i$ being discussed from day $S_i$ to day $E_i$ 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 $X_i$ days to watch series $i$. 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 $d$, Alessandro must have watched completely the tv series which is being talked about by the end of day $d − 1$.

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 $N, D$: the number of TV series that will be discussed and the number of days.
• a line containing the $N$ integers $S_0, . . . , S_{N−1}$.
• a line containing the $N$ integers $E_0, . . . , E_{N−1}$.
• a line containing the $N$ integers $X_0, . . . , X_{N−1}$.

Output data

The output file must contain a single line consisting of integer $K$, the maximum number of days in which Alessandro can discuss TV series with his friends.

Constraints and clarifications

• $1 \leq N \leq 2 \ 000$.
• $1 \leq D \leq 5 \ 000$.
• $1 \leq S_i, E_i, X_i \leq D$ for each $i = 0, 1, . . . N − 1$.
• $Si \leq E_i \leq S_{i+1}$ for each $i = 0, 1, . . . N − 2$.

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 $2$ TV series and $4$ days.

• Series $0$ will be discussed on day $2$ and takes $1$ day to watch.
• Series $1$ will be discussed on days $3$ and $4$ and takes $2$ days to watch.

It is optimal for Alessandro to watch series $1$ on day $1$ and discuss it on day $2$, then watch series $2$ on days $2$ and $3$ and discuss it on day $4$. 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 $4$ TV series and $10$ days.

• Series $0$ will be discussed on day $2$ and takes $1$ day to watch.
• Series $1$ will be discussed on days $3, 4, 5$ and $6$ and takes $4$ days to watch.
• Series $2$ will be discussed on day $7$ and takes $3$ days to watch.
• Series $3$ will be discussed on days $8, 9$ and $10$ and takes $2$ days to watch.

It is optimal for Alessandro to watch series $1$ on days $1, 2, 3$ and $4$, and discuss it on days $5$ and $6$ and to watch series $3$ on days $6$ and $7$, then discuss it on days $8, 9$ and $10$. This will let Alessandro participate to the discussion on $5$ days, and it can be proven that he cannot do better.