Планування багатопроцесорних систем#371

Планування багатопроцесорних систем

2 секунди

64 мегабайти

Дуже складна

На багатопроцесорній машині виконуються дві програми. Кожна програма $i$ ( $i = 1, 2$ i = 1, 2) складається з $N$ процедур, які пронумеровані від $1$ до $N$ і повинні виконуватися послідовно (у порядку $1, \dots, N$ 1, \ldots, N). Процедуру ідентифікує пара $(i, j)$ , де $i = 1, 2$ i = 1, 2 — це номер програми, а $1 \leq j \leq N$ 1 \leq j \leq N — номер процедури всередині програми $i$ . Процедуру $(i, j)$ можна виконати лише на процесорі $P (i, j)$ P(i, j), і її виконання триває $D (i, j)$ D(i, j) секунд. Потрібно розпланувати виконання процедур обох програм так, щоб момент закінчення останньої процедури (у будь-якій програмі) був мінімальним; цей момент називається makespan (тривалість виконання). Обидві програми доступні для планування з часу $0$ .

Планування повинно дотримуватися наступних правил:

Як тільки процедура $(i, j)$ розпочинає виконання на процесорі $P (i, j)$ P(i, j), її не можна переривати до завершення.
Кілька процедур не можуть виконуватися одночасно на одному процесорі, але процедури можуть виконуватися паралельно на різних процесорах.
Виконання процедури $(i, j)$ ( $2 \leq j \leq N$ 2 \leq j \leq N) починається або в момент завершення $(i, j - 1)$ (i, j-1), або будь-коли після цього.
Якщо процедура розпочинається у момент часу $t m$ , вона завершується у момент $t m + D (i, j)$ tm + D(i, j).

Напишіть програму, яка для заданих процедур обох програм знаходить мінімальний makespan.

Вхідні дані

Перший рядок містить $T$ — кількість тестів.

Перший рядок кожного тесту містить число $N$ ( $1 \leq N \leq 300$ 1 \leq N \leq 300) — кількість процедур у кожній програмі. Далі йдуть $N$ рядків для першої програми; $j$ -й з цих рядків містить два цілих числа через пробіл: $P (1, j)$ P(1, j) та $D (1, j)$ D(1, j). Наступні $N$ рядків описують другу програму у тому ж форматі: $j$ -й рядок містить $P (2, j)$ P(2, j) та $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).

Зверніть увагу, що можливо $P (i, j) = P (k, l)$ P(i, j) = P(k, l), тобто процедури $(i, j)$ та $(k, l)$ (k, l) не можуть виконуватись в один і той же час. Якщо $i = k$ i = k, це не має значення, оскільки вони належать одній програмі і повинні виконуватись послідовно.

Вихідні дані

У вихідних даних повинно бути рівно $T$ рядків, у кожному з яких одне число — мінімальний makespan для відповідного тесту. Виводьте відповіді у порядку, в якому дано тести (тобто $i$ -й рядок відповідає $i$ -му тесту).

Приклади

Приклад 1