• testcase23を修正しました。

問題文

HH行、横WW列からなる盤面があります。この盤面の上からii行目、左からjj列目であるマスをマス(i,j)(i, j)とします。

各マス(i,j)(i, j)には整数AijA_{ij}が書かれています。NN個の二つのマスの関係が以下のように与えられます。

  • PiP_i, PjP_j, QiQ_i, QjQ_j が与えられる。この時、マス(Pi,Pj)(P_i, P_j)とマス(Qi,Qj)(Q_i, Q_j)は繋がれている。
  • 繋がれたマスは同じでも構わない。つまり、Pi=QiP_i = Q_i かつ Pj=QjP_j = Q_j でも構わない。
  • 同じ二つのマスについて複数回繋がっても良い。

盤面のスコアを以下のように定義します :

 任意のマス(i,j)(i, j)と繋がっている全てのマスに書かれている整数の和をSSとする。この盤面の存在するすべてのSSに対してSSの最大値。

あなたは与えられた盤面でもう1回二つのマスを選んで繋ぐことができます。二つのマスを適切に選んでスコアを最大化してください。

制約

  • 1H5001 \leq H \leq 500
  • 1W5001 \leq W \leq 500
  • 0N1050 \leq N \leq 10^5
  • 109Aij109-10^9 \leq A_{ij} \leq 10^9 (ただし、1iH1 \leq i \leq H かつ 1jW1 \leq j \leq W)

入力

入力はすべて整数である。

HH WW NN

A11A_{11} A12A_{12} \cdots A1WA_{1W}

A21A_{21} A22A_{22} \cdots A2WA_{2W}

\vdots

AH1A_{H1} AH2A_{H2} \cdots AHWA_{HW}

P1iP_{1i} P1jP_{1j} Q1iQ_{1i} Q1jQ_{1j}

P2iP_{2i} P2jP_{2j} Q2iQ_{2i} Q2jQ_{2j}

\vdots

PNiP_{Ni} PNjP_{Nj} QNiQ_{Ni} QNjQ_{Nj}

出力

盤面のスコアの最大値を出力せよ。

サンプル

入力1
2 2 1
1 2
3 4
1 1 1 2
出力1
7

マス(1,1)(1, 1)とマス(1,2)(1, 2)が繋がれています。現在のスコアはmax(1+2,3,4)=4max(1 + 2, 3, 4) = 4です。

ここでマス(1,2)(1, 2)とマス(2,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
出力2
7
入力3
2 2 2
-1 -2
-3 -4
1 1 2 1
1 2 2 2
出力3
-4
入力4
1 1 0
123
出力4
123

Submit


Go (1.21)