Тур I, Задача 2. "Два конвейера". 40 баллов.

В цехе по производству напитков работают два конвейера. На первом конвейере напиток разливается по бутылкам, а на втором - происходит закупоривание бутылок. После схода с первого конвейера очередной бутылки она сразу же поступает на второй. Поскольку тара используется различная, то каждая бутылка имеет свое время ее заполнения и время закупорки. Требуется написать программу, которая для заданной последовательности бутылок:

1. Определяет время, через которое последняя бутылка в этой последовательности будет закупорена (закупоривать можно лишь наполненные бутылки).
2. Находит такую перестановку заданных бутылок, при которой суммарное время разлива и закупорки бутылок было бы минимально, и определяет это время.

Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 20 секунд

Формат входных данных: В первой строке входного файла содержится целое число N (1<N<1000) - количество бутылок. Далее идут N пар чисел X₁ Y₁ X₂ Y₂ ... X_N Y_N. Здесь X_i означает время разлива, a Y_i - время закупорки бутылки с номером i. Xi и Y_i - неотрицательные целые числа, не превосходящие 1000000. Все числа разделяются пробелами и/или символами перевода строки.

Формат выходных данных: Первая строка выходного файла должна содержать время, требуемое для исходной последовательности бутылок, вторая - минимально возможное время для пункта B задачи. Третья строка должна содержать перестановку номеров бутылок от 1 до N, для которой достигается минимальное время.

Пример файлов входных и выходных данных:

INPUT.TXT	OUTPUT.TXT
3	490
200 40	370
100 100	3 2 1
30 90