Rogan

Prompt please, and I do not know exactly how to implement the algorithm. This olympiad task...

Hey. Please help to solve the task Head John very busy lately. And it does not have time to plan the time of your employees manually. So he asked Jerry programmer to write a program that will calculate how much of a certain type of problems his department will be able to solve in the past month. John knows that to solve this type of problem he needs n employees, each of which will deal with a specific case and can not replace the other. Each of these employees will be engaged in the same task ai hours. Total monthly employee fulfills bi hours. Besides John have Jerry, which can be given to the problem of maximum k hours. Jerry can do the work of any other employee, one hour is equal to one hour of Jerry any other employee. John need to understand how the tasks can be performed per month maximum knowing n, k, a1-n, and b1-n Input data The first line is followed by two positive integers n and k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 109) - the number of employees and number of hours of programmer Jerry. In the second line followed by a sequence a1, a2, ..., an (1 ≤ ai ≤ 109), where the i-th number equals the number of hours the i-th employee, required for solving a problem. The third line should be a sequence of b1, b2, ..., bn (1 ≤ bi ≤ 109), where the i-th number equals the number of hours the i-th employee, who is at John. Output Print a single number - the maximum number of tasks that can make the employees of the department with the help of their available hours and programmer Jerry. Examples: Input data 3 1 2 1 4 11 3 16 The result of 4