Score of Grid

• testcase23を修正しました。

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

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

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

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

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

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

• (ただし、 かつ )

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

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

2 2 1
1 2
3 4
1 1 1 2

7

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

ここでマスとマスを繋ぐことでスコアを7にすることができます。 この以上スコアを増やすことはできないため、答えは7です。

2 2 4
1 2
3 4
1 1 1 1
1 2 1 2 
1 3 1 3 
1 4 1 4

7

2 2 2
-1 -2
-3 -4
1 1 2 1
1 2 2 2

-4

1 1 0
123

123