18965번 - Security Check 다국어

문제

In the airport of Bytetown, there are two long queues waiting for the security check. Checking a person takes one minute, and the two queues can be checked at the same time.

Two teams $A$ and $B$ are going to travel by plane. Each team has $n$ players, ranked from 1ドル$ to $n$ according to their average performance. No two players in the same team share the same rank. Team $A$ is waiting in queue 1ドル$ while team $B$ is waiting in queue 2ドル$. Nobody else is waiting for the security check.

Little Q is the policeman who manages two queues. Every minute, he can either check the first person from one of the queues, or check the first persons from both queues at the same time. He can't change the order in the queues because that will make people unhappy. There is an additional complication, however: if two players $A_i$ and $B_j$ are being checked at the same time, and their ranks are almost the same, specifically $|A_i - B_j| \leq k,ドル they will make a lot of noise. Little Q should never let that happen.

Please write a program to help Little Q find a way to check all the people so that the required time is minimum possible.

입력

The first line of the input contains two integers $n$ and $k$: the number of players in each team and the rank similarity parameter (1ドル \leq n \leq 6 \cdot 10^4,ドル 1ドル \leq k \leq 10$).

The second line contains $n$ distinct integers $A_1, A_2, \ldots, A_n$: the first queue from front to rear (1ドル \leq A_i \leq n$).

The third line contains $n$ distinct integers $B_1, B_2, \ldots, B_n$: the second queue from front to rear (1ドル \leq B_i \leq n$).

출력

Print a single line containing a single integer: the minimum time required to check all the people.

제한

힌트

One possible solution is as follows.

Minute 1: check $A_1$.

Minute 2: check $A_2$.

Minute 3: check $A_3$.

Minute 4: check $A_4$ and $B_1$.

Minute 5: check $B_2$.

Minute 6: check $B_3$.

Minute 7: check $B_4$.