Multi-Machine Scheduling of Two Applications

Time Limit: 10 Seconds    Memory Limit: 131072 KB

Little Ellie has two applications she needs to execute as quickly as possible. Application  i (i=1,2)  consists  of  ns(i)  identical  steps,  numbered  from  1  to  ns(i).  Ellie  owns  a  cluster consisting of  M  machines (numbered from  1  to  M) on which she  can execute the steps of the  2 applications. The machines are not all identical, which means that the  durations of executing one  step  on each machine may be different. To be more precise, it takes  T(i,j)  seconds to execute  one step of application  i  on machine  j.  Because  the steps of each application are  very  CPUintensive, one machine can execute only one step of one application at one time (i.e. if multiple steps of the two applications are scheduled for execution on the same machine, the time intervals during which they are executed must be disjoint or only intersect at their endpoints). Moreover, the execution of any step of any application on any machine cannot be paused and then resumed later (on the same machine or on another machine). This means that  once the execution of a step started on any machine, Ellie can either let the execution complete successfully or cancel it at any time before its completion and restart it later from the beginning (on the same machine or on any other machine).

Because  of  data  dependencies,  the  steps  of  the  same  application  must  be  executed sequentially (i.e. the execution of step  j  of application i  can start only after the execution of step j-1 of that application has finished - either exactly at the same time when the execution of step j-1  finished or at any  later time). The execution  of step  j  can be scheduled  either on the same  machine on which step j-1  was executed or on any other machine. There are no dependencies  between two steps of different applications.

Assuming that Ellie can start executing the steps of the two applications at time moment  0, 

she would like to minimize the time moment TEND (measured in seconds) when the last step of any  application  completes  its  execution.  Please  help  her  by  telling  her  the  minimum  possible value of TEND.

Input

The first line of input contains the number of test cases  T. The  T  test cases are described next.  Each  test  case  consists  of  3  lines.  The  first  line  contains  three  integer  numbers:  ns(1), ns(2) and M. The second line contains M integers, representing, in order: T(1,1), T(1,2), ..., T(1,M).  The  third  line  contains  M  integers,  representing,  in  order:  T(2,1),  T(2,2),  ...,  T(2,M).

Output

For each test case (in the order given in the input), output the minimum possible  value of TEND on a separate line.

Constraints:

•  1 ≤ T ≤ 20

•  1 ≤ ns(i) ≤ 1000000 (106)

•  1 ≤ M ≤ 10

•  1 ≤ T(i,j) ≤ 1000

Sample Input

6
1000000 1000000 1
1
2
999999 999998 5
1 2 3 4 5
5 4 3 2 1
765432 765 2
1 2
1 1000
765432 766 2
1 2
1 1000
3 5 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10 10 5
101 102 103 104 105
101 102 104 105 103

Sample Output

3000000
999999
765432
765433
6
1016
Submit