두 응용 프로그램의 다중 기계 스케줄링

엘리는 응용 프로그램 두 개를 최대한 빨리 실행하려고 한다. 응용 프로그램 $i$($i=1,2$)는 $1$번부터 $ns(i)$번까지 번호가 붙은 동일한 단계 $ns(i)$개로 이루어진다. 엘리의 클러스터에는 $1$번부터 $M$번까지 번호가 붙은 기계 $M$대가 있고, 두 응용 프로그램의 단계를 이 기계에서 실행한다. 기계 성능은 서로 다를 수 있다. 응용 프로그램 $i$의 단계 하나를 기계 $j$에서 실행하면 $T(i,j)$초가 걸린다.

단계 하나하나가 CPU를 많이 쓰기 때문에 기계 한 대는 같은 시각에 단계 하나만 실행한다. 한 기계에 여러 단계를 배정하면 실행 구간이 겹치면 안 되고, 끝점에서만 맞닿을 수 있다. 실행 중인 단계를 잠시 멈췄다가 이어서 실행할 수도 없다. 한 번 시작한 단계는 끝까지 실행하거나, 완료 전에 취소하고 나중에 처음부터 다시 실행한다. 다시 실행하는 기계는 원래 기계여도 되고 다른 기계여도 된다.

데이터 의존성 때문에 같은 응용 프로그램의 단계는 순서대로 실행한다. 응용 프로그램 $i$의 단계 $j$는 단계 $j-1$이 끝난 시각 또는 그보다 늦은 시각에 시작한다. 단계 $j$는 단계 $j-1$을 실행한 기계에서 실행해도 되고 다른 기계에서 실행해도 된다. 서로 다른 응용 프로그램의 단계 사이에는 의존성이 없다.

시각 $0$부터 두 응용 프로그램의 단계를 실행할 수 있다. 두 응용 프로그램을 통틀어 마지막 단계가 끝나는 시각 $TEND$(초)를 최소로 만들려고 한다. $TEND$의 최솟값을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어지고, 각 테스트 케이스는 세 줄로 이루어진다. 첫 줄에는 정수 $ns(1)$, $ns(2)$, $M$이 주어진다. 둘째 줄에는 정수 $M$개 $T(1,1)$, $T(1,2)$, ..., $T(1,M)$이 순서대로 주어진다. 셋째 줄에는 정수 $M$개 $T(2,1)$, $T(2,2)$, ..., $T(2,M)$이 순서대로 주어진다.

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

각 테스트 케이스마다 $TEND$의 최솟값을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

기계가 한 대뿐이면 두 응용 프로그램의 모든 단계가 그 기계에서 차례로 실행되므로 $TEND$는 두 실행 시간의 합이다.

두 응용 프로그램이 서로 다른 기계를 하나씩 쓰면 $TEND$는 두 실행 시간 중 큰 값이다. 다만 두 응용 프로그램이 같은 기계를 원하면 한쪽은 자기에게 더 느린 기계를 써야 한다.

한 응용 프로그램이 끝나면 그 기계가 비고, 남은 응용 프로그램이 그 기계로 옮겨 갈 수 있다. $ns(1)=765432$, $ns(2)=766$, $M=2$, $T(1,1)=1$, $T(1,2)=2$, $T(2,1)=1$, $T(2,2)=1000$인 경우를 보자. 응용 프로그램 1의 모든 단계를 기계 1에서 실행하면 시각 $765432$에 끝난다. 응용 프로그램 2는 앞의 $765$개 단계를 기계 2에서 실행해 시각 $765000$에 끝내고, 기계 1이 빌 때까지 기다렸다가 마지막 단계를 기계 1에서 실행해 시각 $765433$에 끝낸다. 마지막 단계까지 기계 2에서 실행하면 $766000$이 되므로 이 편이 더 빠르다.

두 응용 프로그램이 한 기계를 시간대별로 나누어 쓰면서 각자 여러 기계를 오가는 배치가 가장 빠를 때도 있다.