You have N squirrels, and the i-th squirrel has A_i nuts. You want to minimize the maximum number of nuts any squirrel has. You can perform an operation: take a nut from the i-th squirrel and give it to the j-th squirrel, which costs B_i units of

You are a professional trainer of
N
N squirrels. After a long period of training, they have become remarkably intelligent — they even have their own currency to buy their favorite nuts. You know how many nuts each squirrel has (the i-th squirrel has
A
i
A
i
​
nuts). You've noticed that the overall unhappiness of the squirrels is influenced by the
M
a
x
(
A
1
,
A
2
,
A
3
,
.
.
.
,
A
n
)
Max(A
1
​
,A
2
​
,A
3
​
,...,A
n
​
), so you want to minimize this number. You can perform one operation: take a nut from the
i
−
t
h
i−th squirrel and give it to the
j
−
t
h
j−th squirrel, which will cost you
B
i
B
i
​
units of currency. You can perform this action as many times as you want, as long as you can afford it. Initially, you have
K
K units of currency. Calculate and print the minimum unhappiness level you can achieve.

Input Format
The first line contains two integers —
N
N and
K
K(
1
≤
N
≤
2
∗
1
0
5
1≤N≤2∗10
5
,
0
≤
K
≤
1
0
18
0≤K≤10
18
).

The second line contains
N
N integers
A
i
A
i
​
(
0
≤
A
i
≤
1
0
6
0≤A
i
​
≤10
6
).

The third line contains
N
N integers
B
i
B
i
​
(
0
≤
B
i
≤
1
0
6
0≤B
i
​
≤10
6
).