Factory#4951
There are three machines in the new toy factory: A, B, and C. The factory makes toys by processing each toy on these machines in the order A, B, C. Your task is to create toys as quickly as possible. You know the time to process each toy on each machine: a_i, b_i, and c_i. You may select an arbitrary processing order for the toys. The second machine is so fast that at least one of the following two statements holds: \max(b_i) \leq \min(a_i), or \max(b_i) \leq \min(c_i).
The first line of the input contains the number of toys (1 \leq n \leq 100\,000). The next lines contain three integers each: a_i, b_i, and c_i (1 \leq a_i,\, b_i,\, c_i \leq 1\,000\,000).
Output the minimal possible processing time on the first line. The second line must contain an example of an optimal processing order — a permutation of toy numbers from to .
Example 1