Problem Description

A and B are working on their homework. Today's homework consists of $n$ questions. For the $i$-th question, A takes $a_i$ time to solve it, while B takes $b_i$ time. Because there are too many assignments, they decide to only complete some of them today, and the completed questions are numbered consecutively.

In order to quickly finish all the questions, A and B have even learned the art of cloning and can work on multiple questions at the same time.

They decide to go eat fruits after finishing their homework. B will only go to eat fruits after completing all the planned questions for the day. However, as long as any of A's clones completes the assigned questions, A will immediately go eat fruits.

A only needs $k$ time to finish eating all the fruits. A wants to determine the range of questions in order to finish eating all the fruits without letting B eat any. At the same time, A wants to minimize the total number of questions he has to solve. Can you help him figure out the minimum number of questions he has to solve?

Simplified Statement

Given $n,k$, and sequences $a,b$, find the shortest interval $[i,j]$ such that $\displaystyle(\min_{p=i}^ja_p)+k\leq\max_{p=i}^jb_p$. Output the length of the interval, and if no interval is found, output $-1$.

Constraints

• $1\le n\le 10^5$
• $1\le k\le 10^6$
• $1\le a_i,b_i\le 10^6$

Input

The input is given from Standard Input in the following format:

$n\ \ k\\a_1\ \ a_2\ \ \cdots\ \ a_n\\b_1\ \ b_2\ \ \cdots\ \ b_n$

Output

An integer that represents the minimum number of questions A has to solve. If there is no solution, output $-1$.

Sample Input 1

5 10
8 7 14 8 3
4 2 5 8 2

Sample Output 1

-1

Sample Input 2

5 14
11 22 3 15 6
21 20 17 22 136

Sample Output 2

1

The interval is $[3,3]$ or $[5,5]$, because $a_3+k=3+14=17$ and $a_5+k=6+14=20\lt136$。