Problem Statement

You are going to trade $M$ types of magic stones over $N$ days.

You know the value of each magic stone during the $N$ days.
Specifically, on day $i$, the price of the magic stone of type $j$ is $A_{i, j}$. Here, for $1 \leq i \leq N - 1$, $A_{i, j} \leq A_{i+1, j}$ holds.

On day $i$ $(1 \leq i \leq N)$, you can perform one of the following $3$ types of actions.

• Choose an integer $j$ satisfying $1 \leq j \leq M$ and buy a magic stone of type $j$. Your money decreases by $A_{i, j}$, and the number of magic stones of type $j$ you own increases by $1$.
• Choose an integer $j$ satisfying $1 \leq j \leq M$ and sell a magic stone of type $j$. Your money increases by $A_{i, j}$, and the number of magic stones of type $j$ you own decreases by $1$.
  This action can be performed only if you own at least $1$ magic stone of type $j$.
• Do nothing.

Your money at the start is $10^{100}$, so you will never be unable to buy a magic stone due to a lack of money.

Find the maximum possible difference between your money at the end of day $N$ and your money at the start.

Constraints

• $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)$
• All input values are integers.

Input

The input is given from standard input in the following format.

$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}$

Output

Output the answer to the problem on one line.

Sample

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