0059. Сессия все ближе...

Input file name:	exam.in
Output file name:	exam.out
Time limit:	2 s
Memory limit:	64 megabytes

Профессор и ассистент собираются принимать экзамен по курсу комбинаторных алгоритмов в группе из n студентов. Процедура сдачи экзамена такова: сначала студент j∈1… n (возможно, без подготовки) беседует с ассистентом a_j≥ 0 минут (время беседы зависит от количества пропусков занятий и известно). Ассистент дает ему заранее подготовленную сложную задачу, для решения которой этому студенту будет предоставлено не менее b_j≥ 0 минут, затем несчастный студент отправляется на расправу к профессору, разговор с которым зависит от предшествующих оценок студента и продлится c_j минут. Каждый из экзаменаторов в любой момент времени работает только с одним студентом.

Посоветуйте, в какой очередности бригаде экзаменаторов следует принимать студентов, чтобы как можно быстрее закончить экзамен и со спокойной совестью отправиться пить <<Кока-Колу>>?

Формат входного файла

Исходные данные задачи – число студентов группы 0≤ n≤ 1000 (первая строка исходного файла) и последующие n строк, содержащих по три целых числа 0≤ a_j, b_j, c_j≤ 60 (для j∈1… n).

Формат выходного файла

Результат вычислений – минимальная продолжительность экзамена в минутах.

Пример:

input.txt	output.txt
4 5 2 7 4 4 3 7 3 2 5 1 6	26

Source: Petrozavodsk Winter 2003. Take-Off, Monday, February 03

Discuss       Submit a solution



Printable version