题目描述
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 T_{i} second(s), and one more every P_{i} second(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 T_{i} (i=1..m), respectively.
The third line contains the integers P_{i} (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.
------ Limitations ------
0
0
07
0i,P_{i}≤100
----- Sample Input 1 ------
2
3 2 5
5 1 2
1 2 1
3 2 5
5 1 2
1 1 1
----- Sample Output 1 ------
4
3
----- explanation 1 ------
Test case $1$: Two squirrels wait below trees $2$ and $3$.
- After $1$ second, a chestnut from tree $2$ falls. Total chestnuts the squirrels have is $1$.
- After $2$ seconds, a chestnut from tree $3$ falls. Total chestnuts the squirrels have is $2$.
- After $3$ seconds, two chestnuts fall from trees $2$ and $3$. Total chestnuts the squirrels have is $4$.
- After $4$ seconds, a chestnut from tree $3$ falls. Total chestnuts the squirrels have is $5$.
Total time to gather $5$ chestnuts is $5$ seconds.
Test case $2$: Two squirrels wait below trees $2$ and $3$.
- After $1$ second, a chestnut from tree $2$ falls. Total chestnuts the squirrels have is $1$.
- After $2$ seconds, two chestnuts fall from trees $2$ and $3$. Total chestnuts the squirrels have is $3$.
- After $3$ seconds, two chestnuts fall from trees $2$ and $3$. Total chestnuts the squirrels have is $5$.
Total time to gather $5$ chestnuts is $3$ seconds.
输入格式
见题面
输出格式
见题面