Dope goes to an entertainment plaza and finds an interesting indoor competition .
In this event, There are n buckets and m baskets of gold coins(baskets are clinged to the top of the ceiling).Each of the m baskets start dropping gold coins at Pi'th second(i=1 to m) and the next coin is dropped after every Ti seconds(i=1 to m).Now the task is to collect k gold coins,by placing your given buckets exactly below the baskets(Only one bucket can be placed under one basket and once this is done the timer begins).The person who places his buckets such that they collect k coins in the shortest time possible wins the event.

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 Pi (i=1..m), respectively.
-The third line contains the integers Ti (i=1..m), respectively.

Output

For each test cases, output in a single line an integer which is the shortest
time calculated

Limits:

0<t=1000
0<m,n=10,000
0<k=107
0<Ti,Pi=100

Example

Input:

2
3 2 5
5 1 2
1 2 1
3 2 5
5 1 2
1 1 1

Output:

4
3