• testcase23を修正しました。

問題文


行、横列からなる盤面があります。この盤面の上から行目、左から列目であるマスをマスとします。

各マスには整数が書かれています。個の二つのマスの関係が以下のように与えられます。

  • , , , が与えられる。この時、マスとマスは繋がれている。
  • 繋がれたマスは同じでも構わない。つまり、 かつ でも構わない。
  • 同じ二つのマスについて複数回繋がっても良い。

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

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

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

制約


  • (ただし、 かつ )

入力


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

   

   

   

出力


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

サンプル


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

マスとマスが繋がれています。現在のスコアはです。

ここでマスとマスを繋ぐことでスコアを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.14)