Vaibhav has a crush. But his crush has great attitude and will only accept him as his boyfriend if he fulfills the following conditions for N consecutive days . His crush wants him to give A[ i ] amount of roses for each 1 <= i <= N days. But Vaibhav is a kanjoos guy so he wants to achieve his love by spending minimum amount of money . He has a total of K roses . For each day i , if he gives X roses then he will have to give her B[ i ] chocolates for each of the remaining ( A[ i ] - X ) roses. Help Vaibhav to minimize the maximum amount of chocolates he gives on any day and ouput this value .
INPUT FORMAT
First line contains two integers N and K, the number of days and total number of roses he has.
Second line contains N space seperated integers , the number of roses his crush wants on day i.
Third line contains N space seperated integers , the number of chocolates he has to give for remaining roses on day i .
OUTPUT FORMAT
Print the answer corresponding to the given input.
CONSTRAINTS
1 N 2 x 105
0 K 1012
1 A[ i ] 1 x 106
1 B[ i ] 1 x 106
He has 4 roses in total with him , he will give 1 rose on first day , 0 roses on second day and 3 roses on the third day . So, the remaining roses on each day are { 2,4 2 } respectively. Now , he will give 2*2 = 4 chocolates on first day, 4*1 = 4 chocolates on second day and 2*3 = 6 chocolates on third day. The maximum of { 4,4,6 } is 6 . So, the output is 6 .
Note: He may also distribute 0 roses on the first day , 1 roses on the second day and 3 roses on the third day , which gives the maximum of { 6,3 6 } as 6 .
Author : Rohan Kumar