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.

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

【算法分析】

所谓的01分数规划问题就是指这样的一类问题，给定两个数组，a[i]表示选取i的收益，b[i]表示选取i的代价。如果选取i，定义x[i]=1，否则x[i]=0。

每一个物品只有选或者不选两种方案，求一个选择方案即从其中选取k组a[i]/b[i]，使得R=sigma(a[i]*x[i])/sigma(b[i]*x[i])取得最值，即所有选择物品的总收益/总代价的值最大或是最小。

01分数规划问题主要包含一般的01分数规划、最优比率生成树问题、最优比率环问题等。

来看目标式：

R=sigma(a[i]*x[i])/sigma(b[i]*x[i])

我们的目标是使得R达到最大或者最小，首先定义一个函数

F(L)=sigma(a[i]*x[i])-L*sigma(b[i]*x[i])，显然这只是对目标式的一个简单的变形。

分离参数，得到F(L):=sigma((a[i]-L*b[i])*x[i])，记d[i]=a[i]-L*b[i]，那么F(L):=sigma(d[i]*x[i])。

接下来重点注意一下d[i]和F(L)的单调性。

如果我们已知了L，则所有的的d[i]是已知的，那么这里的贪心策略是为了得到一个最优的F(L)，我们只需要将d[i]排序之后取其中的前k个或者后k个。也就是说，给定L，我们可以直接求出对应的F(L)。

接下来是F(L)，因为b[i]是正的，显然F(L)对于L是单调递减的，这就启发我们可以通过某种方法把F(L)逼近至0，当F(L)=0时，即 sigma(a[i]*x[i])-L*sigma(b[i]*x[i])=0，那么此时的L就是最优值。

然后还要注意到的问题是，我们每次贪心地取d[i]中最小的k个，则最终使得F(L)趋于0的L会是最小的比值；如果每次贪心地取d[i]中最大的k个，则最终使得F(L)趋于0的L会是最大的比值。

考虑F(L):=sigma((a[i]-L*b[i])*x[i])式中，我们取了最后k个di[i]使得F(L)=0，则如果用此时的L去取全部的数，F(L)_tot将是小于零的，也即使得整个F(L)_tot趋于0的L_tot是小于L的。故L是取K组数的情况下，最大的比值。（这段说的有点绕口）

另外再注意到的一点是，如果将a[i]与b[i]上下颠倒，求解的方法相同，结果跟颠倒前也是刚好相对应的。

最后又想到了一个关键点，k的值对最后的结果会是什么影响：

贪心地说，为了使结果尽可能的大，k也要尽可能的大，即尽可能多的舍弃一些，剩下选取的数越少，均值越大

总结F(L)的两个重要性质如下就是：

　1.  F(L)单调递减

　2.  F(max(L)/min(L)) = 0

之后的逼近方法可以有两种选择

1.二分法

二分区间，不断把F(L)逼近至0，若F(L)<0说明L过大，若F(L)>0说明L过小，直到逼近得到一个最优的L；

 /* ***********************************************

 MYID    : Chen Fan

 LANG    : G++

 PROG    : PKU_2976_Erfen

 ************************************************ */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define eps 1e-6

 using namespace std;

 typedef struct nod

 {

     int a,b;

     double r;

 } node;

 bool op(node a,node b)

 {

     return a.r>b.r;

 }

 node p[];

 int main()

 {

     freopen("2976.txt","r",stdin);

     int n,k;

     while(scanf("%d%d",&n,&k))

     {

         if (n==&&k==) break;

         for (int i=;i<=n;i++) scanf("%d",&p[i].a);

         for (int i=;i<=n;i++) scanf("%d",&p[i].b);

         int m=n-k;

         double left=,right=;

         while (left+eps<right)

         {

             double mid=(left+right)/;

             for (int i=;i<=n;i++) p[i].r=p[i].a-mid*p[i].b;

             sort(&p[],&p[n+],op);

             double temp=;

             for (int i=;i<=m;i++) temp+=p[i].r;

             if (temp>) left=mid;

             else right=mid;

         }

         printf("%.0f\n",left*);

     }

     return ;

 }

2.Dinkelbach

从另外一个角度考虑，每次给定一个L，除了我们用来判定的F(L)之外，我们可以通过重新计算得到一个L'，而且能够证明L'一定是更接近最优解的，那么我们可以考虑直接把L移动到L'上去。当L=L'时，说明已经没有更接近最优的解了，则此时的L就是最优解。

注意在Dinkelbach算法中，F(L)仍然是判定是否更接近最优解的工具，也即此时d[i]的选择仍然与之前相同，只是最后移动解的时候是把L直接移往L'

 /* ***********************************************

 MYID    : Chen Fan

 LANG    : G++

 PROG    : PKU_2976_Dinkelbach

 ************************************************ */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #define eps 1e-6

 using namespace std;

 typedef struct nod

 {

     int a,b,index;

     double r;

 } node;

 bool op(node a,node b)

 {

     return a.r>b.r;

 }

 node p[];

 int main()

 {

     freopen("2976.txt","r",stdin);

     int n,k;

     while(scanf("%d%d",&n,&k))

     {

         if (n==&&k==) break;

         for (int i=;i<=n;i++) scanf("%d",&p[i].a);

         for (int i=;i<=n;i++) scanf("%d",&p[i].b);

         int m=n-k;

         double l=,temp=;

         while (fabs(l-temp)>=eps)

         {

             l=temp;

             for (int i=;i<=n;i++) p[i].r=p[i].a-l*p[i].b;

             sort(&p[],&p[n+],op);

             int x=,y=;

             for (int i=;i<=m;i++)

             {

                 x+=p[i].a;

                 y+=p[i].b;

             }

             temp=(double)x/y;

         }

         printf("%.0f\n",temp*);

     }

     return ;

 }