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