Многопроцессорное планирование
На многопроцессорной машине выполняются два приложения. Каждое приложение 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-й тестовый случай из входного файла). Пример ввода/вывода следует.