eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Фабрика

Фабрика

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

На новій фабриці є три станка: A, B, C. Кожна деталь, що виготавляється на фабриці, спочатку обробляється на станку A, а потім на станку B, C. Необхідно виготовити n деталей так, щоб остання деталь була готова якомога раніше. Для кожної деталі відомий час оброки на кожному зі станків: a_i та b_i, c_i. Ви можете вибрати порядок виготовлення. При цьому, другий станок працює настільки швидко, що або max(b_i)min(a_i), або max(b_i)min(c_i).

Вхідні дані

У першому рядку вхідного файлу знаходиться число n - кількість деталей (1n100000). У наоступних n рядках містяться a_i, b_i та c_i - час оброботки деталі під номером i на станках A, B та C відповідно (1a_i, b_i,c_i1000000).

Вихідні дані

У першому рядку вихідного файлу виведіть мінімально можливий час завершення виготовлення останньої деталі. У другому рядку виведіть перестановку чисел від 1 до n - порядок виготовлення деталей.

Приклад

Вхідні дані #1
5
3 1 6
1 1 2
5 2 5
7 1 4
10 2 8
Вихідні дані #1
33
2 1 3 5 4
Автор Dmitry Gozman
Джерело Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007