There are n squirrel(s) waiting below the feet of m chestnut tree(s). The first chestnut of the i-th tree will fall right after Ti second(s), and one more every Pisecond(s) after that. The “big mama” of squirrels wants them to bring their nest no less than k chestnuts to avoid the big storm coming, as fast as possible! So they are discussing to wait below which trees to take enough chestnuts in the shortest time. Time to move to the positions is zero, and the squirrels move nowhere after that.
Request
Calculate the shortest time (how many seconds more) the squirrels can take enough chestnuts.
Input
- The first line contains an integer t, the number of test cases, for each:
- The first line contains the integers m,n,k, respectively.
- The second line contains the integers Ti (i=1..m), respectively.
- The third line contains the integers Pi (i=1..m), respectively.
- (Each integer on a same line is separated by at least one space character, there is no added line between test cases)
Output
For each test cases, output in a single line an integer which is the shortest time calculated.
Example
Input:
2 3 2 5 5 1 2 1 2 1 3 2 5 5 1 2 1 1 1
Output:
4 3
* Explain (case #1): 2 squirrels waiting below the trees 2 and 3.
Limitations
- 0<t≤20
- 0<m,n≤10,000
- 0<k≤107
- 0<Ti,Pi≤100
#include <bits/stdc++.h>
using namespace std;
int T[10005];
int P[10005];
int num[10005];
int k,m,n;
bool cmp(int a,int b)
{return a>b;
}
int ok(int t)
{int i,j;int sum = 0;for(i=1;i<=m;i++){if(T[i] > t){num[i] = 0;continue;}num[i] = (t-T[i])/P[i]+1;if(num[i] > k) return 1;}sort(num+1,num+1+m,cmp);sum = 0;for(i=1;i<=n&&i<=m;i++){sum += num[i];if(sum >= k) return 1;}return 0;}int main()
{int t,i,j;scanf("%d",&t);while(t--){scanf("%d%d%d",&m,&n,&k);for(i=1;i<=m;i++){scanf("%d",&T[i]);}for(i=1;i<=m;i++){scanf("%d",&P[i]);}int l,r,mid;l = 0;r = 2e9;while(l+1>r){mid = (l+r)>>1;if(ok(m)) r = m;else l = m;}if(ok(l)) printf("%d \n",l);else printf("%d \n",r);}return 0;
}