poj 2519 Dropping tests ¶þ·Ö

poj 2519 Dropping tests ¶þ·Ö

Description

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

.<†·Ÿ"http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+R2l2ZW4geW91ciB0ZXN0IHNjb3JlcyBhbmQgYSBwb3NpdGl2ZSBpbnRlZ2VyIDxlbT5rPC9lbT4sIGRldGVybWluZSBob3cgaGlnaCB5b3UgY2FuIG1ha2UgeW91ciBjdW11bGF0aXZlIGF2ZXJhZ2UgaWYgeW91IGFyZSBhbGxvd2VkIHRvIGRyb3AgYW55IDxlbT5rPC9lbT4gb2YgeW91ciB0ZXN0IHNjb3Jlcy48L3A+CjxwPlN1cHBvc2UgeW91IHRha2UgMyB0ZXN0cyB3aXRoIHNjb3JlcyBvZiA1LzUsIDAvMSwgYW5kIDIvNi4gV2l0aG91dCBkcm9wcGluZyBhbnkgdGVzdHMsIHlvdXIgY3VtdWxhdGl2ZSBhdmVyYWdlIGlzIDxpbWcgYWxpZ249"absmiddle" src="http://www.bkjia.com/uploads/allimg/141129/0436093130-1.gif" alt="\">. However, if you drop the third test, your cumulative average becomes .

Input

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 npositive 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.

Output

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.

Sample Input

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

Sample Output

83
100

#include
#include
#include
#include
#include
using namespace std;

struct node{
    double a,b,c;
}s[1005];

bool cmp(node x,node y){
    return x.c>y.c;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0&&m==0)  break;
        int i;
        for(i=0;i>s[i].a;
        for(i=0;i>s[i].b;

        int time=15;
        double r,l,mid;
        r=0;l=100;
        while(time--){
            mid=(r+l)/2;
            for(i=0;i0)  r=mid;
            else   l=mid;
        }
        printf("%.0lf\n",mid);
    }
    return 0;
}