In a certain course, you take *n* tests. If you get *a*_{i} out of *b*_{i} questions correct on test *i*, your cumulative average is defined to be.Given your test scores and a positive integer *k*, determine how high you can make your cumulative average if you are allowed to drop any *k* of your test scores.Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ * n* ≤ 1000 and 0 ≤ * k* < *n*. The second line contains * n* integers indicating *a*_{i} for all *i*. The third line contains * n* positive integers indicating *b*_{i} for all *i*. It is guaranteed that 0 ≤ *a*_{i} ≤ *b*_{i} ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with *n* = *k* = 0 and should not be processed.

For each test case, write a single line with the highest cumulative average possible after dropping *k* of the given test scores. The average should be rounded to the nearest integer.

提交代码