Фабрика#4951
У новій фабриці іграшок є три машини: A, B та C. Фабрика виготовляє іграшки, обробляючи кожну іграшку спочатку на машині A, потім на B, а потім на C. Ваше завдання — максимально швидко виготовити іграшок. Відомий час обробки кожної іграшки на кожній машині: a_i, b_i та c_i. Ви можете обрати будь-який порядок обробки іграшок. Друга машина настільки швидка, що виконується принаймні одна з двох умов: \max(b_i) \leq \min(a_i) або \max(b_i) \leq \min(c_i).
Перший рядок містить число іграшок (1 \leq n \leq 100\,000). Далі йде рядків по три цілих числа: a_i, b_i, c_i (1 \leq a_i,\, b_i,\, c_i \leq 1\,000\,000).
Виведіть у першому рядку мінімальний можливий час обробки. У другому рядку має бути приклад оптимального порядку обробки — перестановка номерів іграшок від до .
Приклад 1