問題文

本当に申し訳ありません。$1$ ケース行の末尾に半角スペースが入っていました。 $N$ 個のお菓子と、$M$ 人の子供がいます。お菓子にはそれぞれ $1,2,\dots ,N$ の番号が、子供にはそれぞれ $1,2,\dots ,M$ の番号がついています。 子供にはそれぞれ幸せ度が存在し, 初めは全ての子供の幸せ度が $0$ です。

今から子供たちは、 $1,2,\dots ,N$ 番目のお菓子について順番に食べるか食べないかを選択していきます。このとき、 $M$ 人の子供たちは全て同じ選択をします。つまりある子供が $i$ 番目のお菓子を食べると、他の子供もみな $i$ 番目のお菓子を食べます。

お菓子 $i$ を子供 $j$ が食べると、それが奇数個目に食べたお菓子であれば幸せ度が $A_{i,j}$ 増加しますが、偶数個目に食べたお菓子であれば幸せ度が $A_{i,j}$ 減少します。

子供たちがそれぞれのお菓子について適切に食べるか食べないか選択していったとき、最終的な幸せ度の合計の最大値を求めてください。 21:35 出力内容を修正しました(幸福度→幸せ度)

入力

$NM$
$A_{1,1}{A}_{1,2}\dots A_{1,M}$
$A_{2,1}{A}_{2,2}\dots A_{2,M}$
$\dots$
$A_{N,1}{A}_{N,2}\dots A_{N,M}$

• 入力は全て整数である。
• $1\le N,M\le 1000={10}^3$
• $1\le A_{i,j}\le {10}^{10}$

出力

あり得る幸せ度の合計値の内最大値を出力して最後に改行してください。

サンプル

4 3
1 2 3
2 3 4
3 4 5
4 5 6

15

1 1
4

4

5 3
3 5 4
74 6 23
234 45 23
76 3 1212
466 3 1

1291