Multi-Machine Scheduling of Two Applications

Ellie wants to finish two applications as early as possible. Application $i$ ($i=1,2$) consists of $ns(i)$ identical steps numbered from $1$ to $ns(i)$. Her cluster holds $M$ machines numbered from $1$ to $M$, and she runs the steps of both applications on them. The machines differ in speed: running one step of application $i$ on machine $j$ takes $T(i,j)$ seconds.

Every step is CPU heavy, so a machine runs at most one step at a time. If several steps are assigned to one machine, their execution intervals must not overlap, and they may touch only at endpoints. A running step cannot be paused and resumed later either. Once a step starts, Ellie either lets it finish or cancels it before completion and runs it again from the beginning later, on the same machine or on another one.

Because of data dependencies, the steps of one application run in order. Step $j$ of application $i$ starts at the moment step $j-1$ of that application finished, or later. Step $j$ may run on the machine that ran step $j-1$ or on any other machine. Steps of different applications do not depend on each other.

Ellie can start executing steps at time $0$. She wants the moment $TEND$ (in seconds) when the last step of either application finishes to be as small as possible. Print the minimum possible value of $TEND$.

The first line contains the number of test cases $T$. The $T$ test cases follow, each on three lines. The first line holds the integers $ns(1)$, $ns(2)$ and $M$. The second line holds the $M$ integers $T(1,1)$, $T(1,2)$, ..., $T(1,M)$ in this order. The third line holds the $M$ integers $T(2,1)$, $T(2,2)$, ..., $T(2,M)$ in this order.

• $1 \le T \le 20$
• $1 \le ns(i) \le 10^6$
• $1 \le M \le 10$
• $1 \le T(i,j) \le 1000$

For each test case, in the order given in the input, print the minimum possible value of $TEND$ on its own line.

With a single machine, every step of both applications runs on it one after another, so $TEND$ is the sum of the two execution times.

If the two applications use one machine each, $TEND$ is the larger of the two execution times. When both applications want the same machine, one of them has to work on a machine that is slower for it.

Once an application finishes, its machine becomes free and the other application can move there. Take $ns(1)=765432$, $ns(2)=766$, $M=2$, $T(1,1)=1$, $T(1,2)=2$, $T(2,1)=1$, $T(2,2)=1000$. Running every step of application 1 on machine 1 finishes it at time $765432$. Application 2 runs its first $765$ steps on machine 2 and finishes them at time $765000$, waits until machine 1 is free, and runs its last step on machine 1, finishing at time $765433$. Keeping the last step on machine 2 would end at $766000$, so the move is faster.

Sometimes the fastest plan lets both applications share one machine over disjoint time intervals while each of them moves across several machines.