题目描述

小明去西部旅游，路过一处沙漠，其中有三处绿洲，将它们分别编号为1,2,3。绿洲i的水价为每升水pi元。可以将水从绿洲i运到绿洲j，运输成本是每升水cij元；运输过程可以直达也可以中转，例如，要从绿洲1运输到绿洲3，路线可以是1->3或者1->2->3。由于水在各个绿洲的价格不同，因此有机会通过在绿洲i买入一些水，再到绿洲j卖出来获利，这样做所能获得的利润就是(绿洲j的水价-绿洲i的水价-运输成本)。

请帮小明通过合理地选择买卖地点和运输路线找到每升水的利润最大的路线。如果这样的路线有多条，优先选择起点（买入点）编号最小的路线；如果仍然有多条，优先选择终点（卖出点）编号最小的路线；如果仍然有多条，优先选择长度最短的路线。

输入描述

第一行包含3个正整数pi，其中第i个数表示绿洲i的每升水的价格。

接下来3行，其中第i行第j个数为cij，表示从绿洲i直达绿洲j的每升水运输成本。

输出描述

第一行一个整数表示每升水最大利润。

接下来一行描述运输路线，依次输出经过的绿洲编号（包含起点和终点）。

100 200 300
0 120 180
50 0 70
100 100 0 

30
2 3 

100 200 300
0 120 170
50 0 70
100 100 0 

30
1 3 

100 200 300
0 90 170
50 0 70
100 100 0

40
1 2 3 

数据范围

【样例1说明】 将水从绿洲2运到绿洲3所能获得的利润是300-200-70=30。不存在利润更高的路线【样例2说明】 获利为30的路线有1->3和2->3两条，根据优先规则选择1->3.【样例3说明】 将水从绿洲1经过绿洲2运到绿洲3所能获得的利润是300-100-(90+70)=40。【数据范围与约定】 对于全部数据，有1<=pi<=10000，0<=cij<=10000,cii=0,至少存在一条利润为正的路线。 测试点1~4(共40分):利润最大的路线是唯一的。 测试点5~10(共60分):无特殊限制。