問題文
Indeed 员工 A 先生玩以下游戏。
垂直长度为 H,水平长度为 W 有一个由 H×W 方块组成的二维板。 从该板的左侧开始 x (1≦x≦W) ,从上面 y (1≦y≦H) 表示为 (x,y) 。
每个方格中都写有一个非负整数。 (x,y) 中写入的数字是 P_{(x,y)} 。
在任何时间点,A 先生都在该板上的某个位置。然后,根据以下规则进行操作。
- 你可以从当前所在的方格垂直和水平移动到相邻的方格。但是,您不能移动它以使其离开板。
- 当您第一次访问某个方块时,您将获得等于该方块上写的数字的分数。
- 当从你当前所在的方格移动到你尚未访问过的方格时,作为移动奖励, 获得(今いるマスに書かれている数)×(次に訪れるマスに書かれている数) 的积分。
- 移动到已经访问过的方块时不会获得积分。
首先,A先生从起点开始。 访问 (S_x,S_y) 。 A先生按照规则自由行动,最终到达目标点,即正方形。 我想要访问 (G_x,G_y) 并完成我的活动。 请注意,一旦您访问了目标点,您可能会再次返回目标点而无需完成操作。
请输出A先生按照规则行动所能获得的最高总分。
入力
输入是按以下格式从标准输入给出的。
[重要]到目前为止,请使用以下输入格式。 我错误地将其写成了 P(x,y) 形式。 它以 P(y,x) 的形式编写。描述已更正。对于给您带来的任何不便,我们深表歉意 (16:01)。
H W
S_x S_y
G_x G_y
P_{(1,1)} P_{(2,1)} … P_{(W,1)}
P_{(1,2)} P_{(2,2)} … P_{(W,2)}
:
P_{(1,H)} P_{(2,H)} … P_{(W,H)}
- 1 线代表板的垂直和水平长度。 2 整数 给出了 H,W (1≦H,W≦100) 用空格分隔。
- 2 线表示起点的坐标。 2 整数 给出了 S_x,S_y (1≦S_x≦W,1≦S_y≦H) 用空格分隔。
- 3 线代表目标点的坐标。 2 整数 给出了 G_x,G_y (1≦G_x≦W,1≦G_y≦H) 用空格分隔。
- 4 从行 H 行提供有关每个方块中写入的数字的信息。这几天之一 i(1≦i≦H) 广场 (1,i),质量 (2,i) ,…,质量 代表 (W,i) 中写入的数字 W 整数 P_{(1,i)},P_{(2,i)},…,P_{(W,i)} 用空格分隔。
- 任何 关于 x,y(1≦x≦W,1≦y≦H) , 在0≦P_{(x,y)}≦100 很满意。 当
出力
1 行中,打印A先生根据规则行动所能获得的最大总分。在输出末尾插入换行符。
入力例1
1 6 2 1 2 1 0 1 2 3 4 0
出力例1
30
起点和终点从左端开始 这是棋盘上的第 2 格。您在该板上可以获得的最高分数是 30 点,这里是实现它的操作示例。
- 作为起点的正方形 访问 (2,1) 。这个方块上写的数字是 1 。此时的总分是 1 点。
- 质量 (3,1) 。这个方块上写的数字是 2 移动奖励是 1×2 点。因此,此时的总得分为 访问 5 点。
- 质量 (4,1) 。这个方块上写的数字是 3 移动奖励是 2×3 点。因此,此时的总得分为 访问 14 点。
- 质量 (5,1) 。此时的总分是 访问 30 点。
- 质量 (4,1) 。由于移动是在已经访问过的方格之间进行的,因此分数没有变化。 访问
- 质量 (3,1) 。同样,分数也没有变化。 访问
- 质量 (2,1) 并完成操作。分数没有变化。最终总成绩为 30 点。
入力例2
3 3 1 1 3 3 2 2 2 1 2 1 1 1 1
出力例2
33
入力例3
10 10 5 2 6 2 31 0 60 19 87 98 35 68 21 41 21 46 85 72 51 13 0 49 19 25 79 82 46 65 30 99 29 44 99 8 39 48 70 99 82 32 25 49 32 54 81 20 57 70 5 40 88 97 56 17 69 54 35 98 7 38 59 91 80 34 28 13 14 28 60 26 82 10 17 100 29 0 27 43 45 88 88 92 21 67 62 33 35 22 26 68 74 95 86 79 68 18 83 72 85 21 72 34 57 77
出力例3
370423