問題文
縦H行、横W列からなる盤面があります。この盤面の上からi行目、左からj列目であるマスをマス(i,j)とします。
各マス(i,j)には整数Aijが書かれています。N個の二つのマスの関係が以下のように与えられます。
- Pi, Pj, Qi, Qj が与えられる。この時、マス(Pi,Pj)とマス(Qi,Qj)は繋がれている。
- 繋がれたマスは同じでも構わない。つまり、Pi=Qi かつ Pj=Qj でも構わない。
- 同じ二つのマスについて複数回繋がっても良い。
盤面のスコアを以下のように定義します :
任意のマス(i,j)と繋がっている全てのマスに書かれている整数の和をSとする。この盤面の存在するすべてのSに対してSの最大値。
あなたは与えられた盤面でもう1回二つのマスを選んで繋ぐことができます。二つのマスを適切に選んでスコアを最大化してください。
制約
- 1≤H≤500
- 1≤W≤500
- 0≤N≤105
- −109≤Aij≤109 (ただし、1≤i≤H かつ 1≤j≤W)
入力
入力はすべて整数である。
出力
盤面のスコアの最大値を出力せよ。
サンプル
マス(1,1)とマス(1,2)が繋がれています。現在のスコアはmax(1+2,3,4)=4です。
ここでマス(1,2)とマス(2,2)を繋ぐことでスコアを7にすることができます。
この以上スコアを増やすことはできないため、答えは7です。
入力2
2 2 4
1 2
3 4
1 1 1 1
1 2 1 2
1 3 1 3
1 4 1 4
入力3
2 2 2
-1 -2
-3 -4
1 1 2 1
1 2 2 2