当前没有测试数据。

题目描述

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

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

输入格式

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

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

输出格式

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

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

样例

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

30
2 3

解释#1

将水从绿洲 $2$ 运到绿洲 $3$ 所能获得的利润是 $300-200-70=30$。不存在利润更高的路线。

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

30
1 3

解释#2

获利为 $30$ 的路线有 $1\rightarrow 3$ 和 $2\rightarrow 3$ 两条，根据优先规则选择 $1\rightarrow 3$。

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

40
1 2 3

解释#3

将水从绿洲 $1$ 经过绿洲 $2$ 运到绿洲 $3$ 所能获得的利润是 $300-100-(90+70)=40$。

数据范围

• 对于全部数据，有 $1\le p_i\le 10000$，$0\le c_{ij}\le 10000$，$c_{ii}=0$，至少存在一条利润为正的路线。
• 测试点 $1\sim 4$（共 $40$ 分）：利润最大的路线是唯一的。
• 测试点 $5\sim 10$（共 $60$ 分）：无特殊限制。