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

Dmitry Gozman Contest 1. Petrozavodsk training camp. Winter 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. 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
To submit the solution for this problem go to the Problem set: 1522. Factory