Multiprocessor Scheduling#371

Multiprocessor Scheduling

2 seconds

64 megabytes

Very hard

There are two applications running on a multiprocessor machine. Each application $i$ ( $i = 1, 2$ i = 1, 2) consists of $N$ procedures, which are numbered from $1$ to $N$ and must be executed sequentially (in the order $1, \dots, N$ 1, \ldots, N). A procedure is identified by a pair $(i, j)$ , where $i = 1, 2$ i = 1, 2 identifies the application, and $1 \leq j \leq N$ 1 \leq j \leq N is the procedure index within application $i$ . Procedure $(i, j)$ can only be executed on processor $P (i, j)$ P(i, j) and its execution lasts $D (i, j)$ D(i, j) seconds. We want to schedule the procedures of both applications so that the moment the last procedure finishes (in either application) is minimized; this moment is called the makespan. Both applications are available for scheduling from time $0$ .

The scheduling must follow these rules:

Once a procedure $(i, j)$ starts executing on processor $P (i, j)$ P(i, j), it cannot be interrupted until it finishes.
Multiple procedures cannot be executed simultaneously on the same processor, but procedures may be executed in parallel on different processors.
The execution of procedure $(i, j)$ ( $2 \leq j \leq N$ 2 \leq j \leq N) starts either at the moment when $(i, j - 1)$ (i, j-1) finishes, or any time after.
If a procedure starts at time $t m$ , it finishes at time $t m + D (i, j)$ tm + D(i, j).

Write a program that, given the procedures of both applications, finds the minimum makespan.

Input

The first line contains $T$ — the number of test cases.

The first line of each test case contains the number $N$ ( $1 \leq N \leq 300$ 1 \leq N \leq 300), the number of procedures in each application. Then $N$ lines follow for the first application; the $j$ -th of these lines contains two integers separated by a space: $P (1, j)$ P(1, j) and $D (1, j)$ D(1, j). After that, the next $N$ lines describe the second application, in the same format: the $j$ -th line contains $P (2, j)$ P(2, j) and $D (2, j)$ D(2, j). $1 \leq P (i, j) \leq 10$ 1 \leq P(i, j) \leq 10, $1 \leq D (i, j) \leq 15000$ 1 \leq D(i, j) \leq 15000 ( $i = 1, 2$ i = 1, 2; $1 \leq j \leq N$ 1 \leq j \leq N).

Note that it is possible that $P (i, j) = P (k, l)$ P(i, j) = P(k, l), which means procedures $(i, j)$ and $(k, l)$ (k, l) cannot overlap in time. If $i = k$ i = k, this does not matter, since those belong to the same application and must be executed sequentially.

Output

The output must contain exactly $T$ lines, each containing a single number — the minimum makespan for the corresponding test case. Print the answers in the order given in the input (i.e., the $i$ -th line corresponds to the $i$ -th test case).

Examples

Example 1