Vaibhav And His Crush

5

1 votes
Problem

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

 N  2 x 105

 K  1012

 A[ i ]  1 x 106

 B[ i ]  1 x 106

Sample Input
3 4
3 4 5
2 1 3
Sample Output
6
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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

Editor Image

?