ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1522. Factory

Time limit: 2.0 second
Memory limit: 64 MB
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).

Input

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

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.

Samples

inputoutput
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
Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007