Emiya is a high school student who excels at cooking. He can prepare $m$ different dishes. One day, Yaz, Zid, and their $n$ friends visit his home, and Emiya needs to prepare some dishes to host them.

Yaz and Zid will eat anything, but their friends are somewhat picky. Specifically, we use integers $a_{i,j} \geq -1$ to represent the attitude of the $i$-th friend toward the $j$-th dish:

• If $a_{i,j} \geq 0$, the $i$-th friend does not dislike this dish. If this dish is on the table and there are no other dishes that this friend dislikes, they will leave Emiya a red envelope of $a_{i,j}$ as a token of appreciation and gratitude.
• If $a_{i,j} = -1$, the $i$-th friend dislikes this dish. If this dish is on the table, the friend will be very angry and leave the table immediately. This means they will not leave a red envelope for any dish.

Emiya is good at cooking but not at calculating. Please help Emiya select a set of dishes to maximize the total amount of money received in red envelopes. For convenience, you only need to output this maximum total sum.

Input

The input is read from standard input.

The first line contains two integers $n$ and $m$, as described in the problem statement.

The next $n$ lines each contain $m$ integers. The $j$-th integer in the $(i+1)$-th line is $a_{i,j}$, as described in the problem statement.

It is guaranteed that $n, m \geq 1$ and $a_{i,j} \geq -1$.

Output

Output to standard output.

A single integer representing the maximum total sum of the red envelopes.

Examples

Input 1

3 3
1 2 3
2 -1 100
100 10 -1

Output 1

113

Note 1

The optimal strategy is to prepare the 1st and 2nd dishes. If this is done, although the 2nd guest will leave in anger, the total amount of red envelopes left by the other two guests is maximized.

Input 2

See ex_2.in and ex_2.ans in the download directory.

Output 2

See ex_2.in and ex_2.ans in the download directory.

Input 3

See ex_3.in and ex_3.ans in the download directory.

Output 3

See ex_3.in and ex_3.ans in the download directory.

Subtasks

This problem has 4 subtasks:

• Subtask 1 (20 points): Special constraint: $n \leq 10, m \leq 2000$.
• Subtask 2 (20 points): Special constraint: $n \leq 14$.
• Subtask 3 (20 points): Special constraint: For each friend, the indices of the dishes they dislike form a single interval. That is, for each guest $i$, there exist integers $l, r$ ($l \leq r$) such that $a_{i,j} = -1$ if and only if $j \in [l, r]$.
• Subtask 4 (40 points): No special constraints.

For all test cases, it is guaranteed that $n \leq 20$, $m \leq 10^6$, and $a_{i,j} \leq 10^9$.

Note

Some test cases have large input sizes; please pay attention to the I/O efficiency of your program.