题目描述

在某个课程中，你需要进行 $n$ 次测试。

如果你在共计$b_i$道题的测试$i$上的答对题目数量为 $a_i$，你的累积平均成绩就被定义为

$$100*\frac{\textstyle\sum_{i=1}^{n}a_i}{\textstyle\sum_{i=1}^{n}b_i} $$

给定您的考试成绩和一个正整数$k$，如果您被允许放弃任何 $k$ 门考试成绩，您的累积平均成绩的可能最大值是多少。

假设您进行了 3 次测试，成绩分别为 5/5,0/1 和 2/6。

在不放弃任何测试成绩的情况下，您的累积平均成绩是:$100*\frac{5+0+2}{5+1+6}=50$

然而，如果你放弃第三门成绩，则您的累积平均成绩就变成了$100*\frac{5+0}{5+1}\approx 83.33\approx 83$

输入格式

输入包含多组测试用例，每个测试用例包含三行。

对于每组测试用例，第一行包含两个整数 $n$ 和$k$。

第二行包含$n$ 个整数，表示所有的$a_i$。

第三行包含 n 个整数，表示所有的 bi。

当输入用例 $n=k=0$ 时，表示输入终止，且该用例无需处理。

输出格式

对于每个测试用例，输出一行结果，表示在放弃 k 门成绩的情况下，可能的累积平均成绩最大值。

结果应四舍五入到最接近的整数。

样例

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

83
100

数据范围

$1≤n≤1000, 0≤k<n, 0≤a_i≤b_i≤10^9$

来源

• POJ2976
• 算法竞赛进阶指南