ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Dmitry Gozman Contest 1. Petrozavodsk training camp. Winter 2007

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Factory

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
There are three machines on the new toy factory: A, B and C. The factory makes toys by processing each toy on these machines in order A, B, C. Your task is to create N toys as soon as possible. You know the time to process each toy on each machine: ai, bi and ci. You can select an arbitrary order of processing toys. The second machine is so fast that at least one of the following two statements holds: max(bi) ≤ min(ai) or max(bi) ≤ min(ci).

Исходные данные

The first line of the input contains the number of toys N (1 ≤ N ≤ 105). The next N lines contain three integers each: ai, bi and ci (1 ≤ ai, bi, ci ≤ 106).

Результат

Output the minimal possible processing time on the first line. The second line must contain an example of optimal processing order — a permutation of toy numbers from 1 to N.

Примеры

исходные данныерезультат
5      
3 1 6   
1 1 2   
5 2 5   
7 1 4   
10 2 8  
33
2 1 3 5 4 
1      
5 4 7   
16
1
Автор задачи: Dmitry Gozman
Источник задачи: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1522. Factory