問題文

あなたは、$N$ 日間にわたって $M$ 種類の魔法石の売買を行おうとしています。

あなたは、$N$ 日間におけるそれぞれの魔法石の価値が分かっています。
具体的には、$i$ 日目について、$j$ 種類目の魔法石の値段は $A_{i, j}$ です。ここで、$1 \leq i \leq N - 1$ について、$A_{i, j} \leq A_{i+1, j}$ が成り立ちます。

あなたは、$i$ $(1 \leq i \leq N)$ 日目には $3$ 種類の行動のいずれかを行うことができます。

• $1 \leq j \leq M$ を満たす整数 $j$ を選び、$j$ 種類目の魔法石を買う。この時、所持金が $A_{i, j}$ だけ減少し、$j$ 種類目の魔法石の所持数が $1$ だけ増加する。
• $1 \leq j \leq M$ を満たす整数 $j$ を選び、$j$ 種類目の魔法石を売る。この時、所持金が $A_{i, j}$ だけ増加し、$j$ 種類目の魔法石の所持数が $1$ だけ減少する。
  この行動は、$j$ 種類目の魔法石を $1$ つ以上所持している場合に限り行うことができる。
• 何もしない。

あなたの開始時点の所持金は $10^{100}$ であるため、所持金の都合で魔法石が買えなくなることはありません。

$N$ 日目が終わった時点での所持金と開始時点での所持金の差の最大値を求めてください。

制約

• $1 \leq N, M$
• $N \times M \leq 3000$
• $1 \leq A_{i, j} \leq 10^{9}$
• $A_{i, j} \leq A_{i+1, j}$ $(1 \leq i \leq N - 1)$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$
$A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, M}$
$A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, M}$
$\vdots$
$A_{N, 1}$ $A_{N, 2}$ $\cdots$ $A_{N, M}$

出力

問題の答えを一行に出力せよ。

サンプル

4 2
100 100
200 150
300 350
400 400

500

5 3
100 100 100
200 100 100
300 100 100
400 100 100
500 100 100

600