Планування багатопроцесорних систем
На багатопроцесорній машині виконуються дві програми. Кожна програма i (i=1,2) складається з N процедур, які пронумеровані від 1 до N і повинні виконуватися послідовно (в порядку 1,…,N). Процедура ідентифікується парою (i,j), де i=1,2 вказує на програму, а 1≤j≤N представляє індекс процедури в послідовності програм i. Процедура (i,j) може виконуватися лише на процесорі P(i,j) машини, і її виконання триває D(i,j) секунд. Ми прагнемо спланувати виконання процедур двох програм на процесорах так, щоб момент завершення останньої процедури (з будь-якої з двох програм) був мінімальним; цей момент називається makespan. Вважаємо, що обидві програми доступні для планування з моменту часу 0. Розклад повинен дотримуватися таких правил:
Як тільки починається виконання процедури (i,j) на процесорі P(i,j), її не можна перервати до завершення.
На одному процесорі не можна виконувати кілька процедур одночасно, але можна виконувати кілька процедур паралельно на різних процесорах.
Виконання процедури (i,j) (2≤j≤N) починається або в точний момент часу tm, коли процедура (i,j-1) закінчує своє виконання, або в будь-який момент після tm.
Якщо процедура починає своє виконання в момент часу tm, то вона завершиться в момент часу tm+D(i,j).
Напишіть програму, яка, маючи інформацію про процедури двох програм, обчислює мінімальний makespan.
Перша строка вхідного файлу містить число T тестових випадків, які описані далі. Перша строка кожного тестового випадку містить число N (1≤N≤300) процедур, що складають кожну з двох програм. Далі йдуть N рядків, що описують першу програму. j-й з цих N рядків містить два цілі числа, розділені пробілом: P(1,j) та D(1,j). Після цього йдуть інші N рядків, що описують другу програму. j-й з цих N рядків містить два цілі числа, розділені пробілом: P(2,j) та D(2,j). Маємо 1≤P(i,j)≤10 та 1≤D(i,j)≤15000 (i=1,2; 1≤j≤N). Зверніть увагу, що може бути P(i,j)=P(k,l) — це означає, що процедури (i,j) та (k,l) не можуть виконуватися в перекриваючихся інтервалах часу (зверніть також увагу, що якщо i=k, це не має значення, оскільки процедури однієї програми повинні виконуватися послідовно).
Вихідний файл повинен містити рівно T рядків з одним числом у кожному — мінімальний makespan для відповідного тесту з вхідного файлу. Ці відповіді повинні бути надруковані в порядку, в якому тестові випадки дані у вхідному файлі (тобто i-й рядок вихідного файлу містить відповідь на i-й тестовий випадок з вхідного файлу). Нижче наведено приклад вхідних/вихідних даних.