Problem Description

DISCO presents Discovery Channel Programming Contest 2016 Finals' DDPC Special Buffet time has begun. You are about to go and place dishes on an empty tray. There are $N$ types of dishes at the DDPC Special Buffet. The $i$-th type of dish will be gone $T_i$ seconds after the buffet starts, and its deliciousness is $A_i$.

There are some special rules at the DDPC Special Buffet:

• You must spend $1$ second to place one type of dish on the tray. That is, if you start placing a dish at time $s$, you will finish placing it at time $s+1$.
• You must not place the same type of dish that was previously placed on the tray.
• You cannot place the $i$-th type of dish on the tray if the current time $s$ does not satisfy $s+1 \leq T_i$.

You decided to return to your seat once the total deliciousness of the dishes on the tray reaches or exceeds $X$. Find the minimum time $t$ at which it is possible to make the total deliciousness of the dishes on the tray reach or exceed $X$.

Input Format

The input is given from the standard input in the following format:

$N$ $X$ $T_1$ $T_2$ … $T_N$ $A_1$ $A_2$ … $A_N$

• The first line contains an integer $N$ (the number of types of dishes at the DDPC Special Buffet, $1 \leq N \leq 10^5$) and an integer $X$ (the target total deliciousness of the dishes on the tray, $1 \leq X \leq 10^9$), separated by spaces.
• The second line contains $N$ integers $T_i$ (the time when the $i$-th type of dish will be gone, $1 \leq T_i \leq 10^5$), separated by spaces.
• The third line contains $N$ integers $A_i$ (the deliciousness of the $i$-th type of dish, $1 \leq A_i \leq 10^5$), separated by spaces.

Output Format

Output the minimum time $t$ at which it is possible to make the total deliciousness of the dishes on the tray reach or exceed $X$. If it is impossible, output -1. Do not forget to add a newline at the end.

Sample Input and Output

Sample Input #1

4 5
1 2 3 4
3 3 1 1

Sample Output #1

2

Sample Input #2

3 10
1 2 3
3 3 4

Sample Output #2

3

Sample Input #3

3 5
9 9 4
2 2 6

Sample Output #3

1

Sample Input #4

5 101
1 2 3 4 5
20 20 20 20 20

Sample Output #4

-1

Sample Input #5

2 2
1 1
1 1

Sample Output #5

-1

Sample Input #6

4 6
1 1 2 2
3 4 1 2

Sample Output #6

2

Sample Input #7

3 4
1 2 2
1 2 2

Sample Output #7

2

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $T_i < T_j$ implies $A_i \geq A_j$, you will get $10$ points.
• If you solve the dataset without additional constraints, you will get an additional $40$ points, totaling $50$ points.

Sample Explanation 1

• By taking dishes in the following way, it is possible to make the total deliciousness of the dishes on the tray reach or exceed $5$ at time $2$.
• At $0$ seconds, the total deliciousness of the dishes on the tray is $0$. Place the $1$-st type of dish on the tray.
• At $1$ second, the total deliciousness of the dishes on the tray is $3$. Place the $2$-nd type of dish on the tray.
• At $2$ seconds, the total deliciousness of the dishes on the tray is $6$.
• This case satisfies the additional constraints for partial points.

Sample Explanation 2

• By taking dishes in the following way, it is possible to make the total deliciousness of the dishes on the tray reach or exceed $10$ at time $3$.
• At $0$ seconds, the total deliciousness of the dishes on the tray is $0$. Place the $1$-st type of dish on the tray.
• At $1$ second, the total deliciousness of the dishes on the tray is $3$. Place the $2$-nd type of dish on the tray.
• At $2$ seconds, the total deliciousness of the dishes on the tray is $6$. Place the $3$-rd type of dish on the tray.
• At $3$ seconds, the total deliciousness of the dishes on the tray is $10$.
• This case does not satisfy the additional constraints for partial points.

Sample Explanation 3

• By taking dishes in the following way, it is possible to make the total deliciousness of the dishes on the tray reach or exceed $5$ at time $1$.
• At $0$ seconds, the total deliciousness of the dishes on the tray is $0$. Place the $3$-rd type of dish on the tray.
• At $1$ second, the total deliciousness of the dishes on the tray is $6$.
• This case satisfies the additional constraints for partial points.

Sample Explanation 4

• No matter how dishes are taken, it is impossible to make the total deliciousness of the dishes on the tray reach or exceed $101$.
• This case satisfies the additional constraints for partial points.

Sample Explanation 5

• No matter which dish is taken at time $0$, the other dish will be gone at time $1$, so it is impossible to make the total deliciousness of the dishes on the tray reach or exceed $2$.
• This case satisfies the additional constraints for partial points.

Sample Explanation 6

• By taking dishes in the following way, it is possible to make the total deliciousness of the dishes on the tray reach or exceed $6$ at time $2$.
• At $0$ seconds, the total deliciousness of the dishes on the tray is $0$. Place the $2$-nd type of dish on the tray.
• At $1$ second, the total deliciousness of the dishes on the tray is $4$. Place the $4$-th type of dish on the tray.
• At $2$ seconds, the total deliciousness of the dishes on the tray is $6$.
• This case satisfies the additional constraints for partial points.

Sample Explanation 7

• By taking dishes in the following way, it is possible to make the total deliciousness of the dishes on the tray reach or exceed $4$ at time $2$.
• At $0$ seconds, the total deliciousness of the dishes on the tray is $0$. Place the $2$-nd type of dish on the tray.
• At $1$ second, the total deliciousness of the dishes on the tray is $2$. Place the $3$-rd type of dish on the tray.
• At $2$ seconds, the total deliciousness of the dishes on the tray is $4$.
• This case does not satisfy the additional constraints for partial points.

见题面 Input 部分

见题面 Output 部分