На фабрике производятся N игрушек разных типов. Для каждой игрушки известна длительность её сборки и длительность упаковки (в минутах). Все игрушки пронумерованы начиная с единицы. Параллельная сборка или упаковка игрушек не предусмотрена. Нулевая минута соответствует началу смены на фабрике, длительность смены составляет 14 ч.
Специальный аппарат обрабатывает игрушки по следующему алгоритму:
– аппарат упорядочивает все игрушки таким образом, чтобы собрать и упаковать как можно больше игрушек за смену;
– аппарат собирает игрушку;
– после сборки аппарат упаковывает игрушку;
– после упаковки аппарат приступает к сборке следующей игрушки;
– если аппарат не успеет завершить работу (сборку и упаковку) игрушки до конца смены, то она не принимается во внимание.
Этот алгоритм применяется последовательно для всех N игрушек.
Определите, какое минимальное время потребуется для сборки и упаковки всех игрушек, которые будут обработаны за смену и какой номер будет иметь последняя собранная и упакованная аппаратом игрушка в этом случае.
Если способов выбрать последнюю игрушку несколько, необходимо выбрать игрушку, время обработки которой будет меньше.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество игрушек. Следующие N строк содержат пары чисел, обозначающих соответственно длительность сборки и длительность упаковки конкретной игрушки (в минутах).
Запишите в ответе два натуральных числа: минимальное время, которое потребуется для сборки и упаковки всех игрушек за смену, а также номер последней обработанной аппаратом игрушки в этом случае.
Типовой пример организации данных во входном файле
5
30 50
100 155
150 170
10 160
120 55
При таких исходных данных минимальное время сборки и упаковки игрушек за смену составит 680, при этом последней будет собрана и упакована игрушка под номером 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.