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.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+R2l2ZW4geW91ciB0ZXN0IHNjb3JlcyBhbmQgYSBwb3NpdGl2ZSBpbnRlZ2VyIDxlbT5rPC9lbT4sIGRldGVybWluZSBob3cgaGlnaCB5b3UgY2FuIG1ha2UgeW91ciBjdW11bGF0aXZlIGF2ZXJhZ2UgaWYgeW91IGFyZSBhbGxvd2VkIHRvIGRyb3AgYW55IDxlbT5rPC9lbT4gb2YgeW91ciB0ZXN0IHNjb3Jlcy48L3A+CjxwPlN1cHBvc2UgeW91IHRha2UgMyB0ZXN0cyB3aXRoIHNjb3JlcyBvZiA1LzUsIDAvMSwgYW5kIDIvNi4gV2l0aG91dCBkcm9wcGluZyBhbnkgdGVzdHMsIHlvdXIgY3VtdWxhdGl2ZSBhdmVyYWdlIGlzIDxpbWcgYWxpZ249"absmiddle" src="https://www.cppentry.com/upload_files/article/49/1_gehgh__.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;i
         
          0) r=mid; else l=mid; } printf("%.0lf\n",mid); } return 0; }