Фабрика
На новой фабрике есть три станка: 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 - количество деталей (1 ≤ n ≤ 100000). В последующих n строках содержатся a_i, b_i и c_i - время обработки детали с номером i на станках A, B и C соответственно (1 ≤ a_i, b_i,c_i ≤ 1000000).
Выходные данные
В первую строку выходного файла выведите минимальное возможное время окончания изготовления последней детали. Во второй строке выведите перестановку чисел от 1 до n - порядок изготовления деталей.