题目描述

在某门课程中，你参加了$n$次考试。在第$i$次考试中，你答对了$a_i$道题，总共有$b_i$道题。你的累计平均分定义为所有考试答对题数之和除以总题数之和。

给定你的考试成绩和一个正整数$k$，确定在允许你放弃任意$k$次考试成绩的情况下，你的累计平均分最高可以达到多少。

例如：
假设你参加了3次考试，成绩分别为5/5、0/1、2/6。如果不放弃任何考试，你的累计平均分为 $\frac{5+0+2}{5+1+6} \approx58.33\%$。但如果放弃第三次考试（2/6），你的累计平均分变为 $\frac{5+0}{5+1} \approx83.33\%$。

输入格式

输入文件包含多个测试用例，每个测试用例由三行组成：

• 第一行：两个整数$n$和$k$（$1 \leq n \leq1000$，$0 \leq k <n$）。
• 第二行：包含$n$个整数$a_1,a_2,…,a_n$（$0 \leq a_i \leq b_i \leq10^9$）。
• 第三行：包含$n$个正整数$b_1,b_2,…,b_n$。

输入的结束标记为一行包含两个$0$的测试用例（即$n=0,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  

提示

为了避免四舍五入误差导致的歧义，测试数据保证所有答案与边界值相差至少0.001（例如不会出现83.4997的情况）。

题目来源

2005年斯坦福大学本地竞赛