/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
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