2998: (2007女生赛) 全能的福娃

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

  四年一度的奥运会里,其中有两个特别的比赛项目,分别称作“十项全能”(男子)和“七项全能”(女子),属于田径运动综合性比赛项目,是对田径运动员全面性检验的比赛。   而在卡通世界里面,卡通人物们可谓是无所不能。现在,卡通界也举办了一个奥运会,其中也有一个叫做为“X—全能”的比赛项目。而我们的福娃们也参加了这个比赛。   这个全能比赛跟我们人类的全能比赛有所不同,它是团体比赛,并且它所包含的比赛项目数会因每队参加比赛的卡通人物数量不同而划分出来不同的组别,每位队员只能参加一个比赛项目。例如,我们的五位福娃就参加了其中的“5—全能”组别的比赛。他们需要先后经过长跑,骑自行车,游泳,攀岩以及竞走总共5个项目来进行比赛的角逐。   对于每一支参加全能比赛的队伍而言,每位队员都是有实力来应付全能比赛里不同项目的比赛的。但实际上,每位队员也是有自己较为擅长的项目和相对较弱的项目。因此,安排好不同的队员参加不同的比赛项目,对于夺冠来说是一个至关重要的策略。   例如,“贝贝”擅长于攀岩,“欢欢”更擅长于长跑而“迎迎”则更擅长于竞走。        

现在某X—全能参赛队有X个队员,给定你这个队伍所有队员参加不同比赛项目的能力值,要求做出最具夺冠实力的队员安排(即总能力值最大),使该队能以最佳的状态出赛。

Input

  输入有多组数据,每组数据的第一行输入X( 0<=X<=7 ),表示某队伍有X位队员,他们要参加“X—全能”组别的比赛。当X输入为0时表示输入结束。  接下来X行,每行输入有X个正整数。输入的第i行的第j个正整数K,表示队员i参加第j个项目的能力值为K。

Output

  每组数据,第一行输出,团队参加比赛最大的总能力值。  第二行输出X个数字,表示具体的队员安排。( 如输出“3 1 2”,则表示第一个队员参加第三个项目,第二个队员参加第1个项目,第三名队员参加第二个项目。)

Sample Input Copy

5<br/>10 6 3 7 4<br/>5 7 10 4 1<br/>9 10 8 7 6<br/>1 2 3 10 4<br/>5 5 5 5 10<br/>0<br/>

Sample Output Copy

50<br/>1 3 2 4 5<br/><br/>