다중 프로세서 스케줄링

다중 프로세서 컴퓨터에서 두 개의 응용 프로그램이 실행된다. 각 응용 프로그램 $i$ ($i = 1, 2$)는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 프로시저로 이루어지며, 이 프로시저들은 반드시 $1, 2, \ldots, N$의 순서대로 차례로 실행되어야 한다. 프로시저는 쌍 $(i, j)$로 나타내며, $i \in \{1, 2\}$는 응용 프로그램을, $1 \le j \le N$은 응용 프로그램 $i$ 안에서의 순서를 뜻한다. 프로시저 $(i, j)$는 오직 프로세서 $P(i, j)$에서만 실행할 수 있고, 실행에는 $D(i, j)$초가 걸린다.

두 응용 프로그램의 모든 프로시저를 프로세서에 배치하여, 두 응용 프로그램 중 마지막 프로시저가 끝나는 시각(메이크스팬, makespan)을 최소로 만들어라. 두 응용 프로그램은 모두 시각 $0$부터 스케줄링할 수 있다. 올바른 스케줄은 다음 규칙을 지켜야 한다.

• 프로시저 $(i, j)$가 프로세서 $P(i, j)$에서 실행을 시작하면, 끝날 때까지 중간에 멈출 수 없다.
• 한 프로세서는 같은 시각에 최대 한 개의 프로시저만 실행할 수 있지만, 서로 다른 프로세서는 프로시저를 동시에 병렬로 실행할 수 있다.
• $2 \le j \le N$인 프로시저 $(i, j)$는 프로시저 $(i, j-1)$이 끝나는 시각 또는 그 이후의 임의의 시각에 시작할 수 있다.
• 시각 $t$에 시작한 프로시저는 시각 $t + D(i, j)$에 끝난다.

두 응용 프로그램의 프로시저 정보가 주어질 때, 가능한 최소 메이크스팬을 구하여라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에는 각 응용 프로그램의 프로시저 개수 $N$ ($1 \le N \le 300$)이 주어진다. 이어지는 $N$개의 줄에는 첫 번째 응용 프로그램이 주어지며, 그중 $j$번째 줄에는 두 정수 $P(1, j)$와 $D(1, j)$가 공백으로 구분되어 주어진다. 그다음 $N$개의 줄에는 같은 형식으로 두 번째 응용 프로그램의 $P(2, j)$와 $D(2, j)$가 주어진다.

모든 값은 $1 \le P(i, j) \le 10$과 $1 \le D(i, j) \le 15000$을 만족한다. $P(i, j)$와 $P(k, l)$이 같을 수도 있음에 유의하라. 두 프로시저가 같은 프로세서를 사용하면 겹치는 시간 구간에 실행될 수 없다. 같은 응용 프로그램의 프로시저는 이미 순차적으로 실행되므로, 이 제약은 서로 다른 두 응용 프로그램 사이에서만 의미가 있다.

각 테스트 케이스마다 최소 메이크스팬을 한 줄에 하나씩 출력한다. 답은 입력에 주어진 테스트 케이스의 순서와 같은 순서로 출력한다.