Background

Because the testdata size of this problem is large, only part of the testdata will be judged for this problem. The remaining testdata can be submitted and tested at U412486.

Problem Description

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

Yaz and Zid eat anything, but some of their friends are picky. Specifically, we use an integer $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$, then the $i$-th friend does not hate this dish. If this dish is on the table, and there is no other dish that this friend hates, then he will leave Emiya a red envelope of $a_{i,j}$ yuan to show praise and thanks.

• If $a_{i,j} = -1$, then the $i$-th friend hates this dish. If this dish is on the table, then this friend will get very angry and leave immediately. This means he will not leave any red envelope for any dish.

Emiya is good at cooking but not good at calculations. Please help Emiya choose some dishes so that the total amount of red envelopes he receives is maximized. For convenience, you only need to output this maximum total sum.

Input Format

The first line contains two integers $n,m$, as described above.

Lines $2$ to $n+1$ each contain $m$ integers: in line $i+1$, the $j$-th integer is $a_{i,j}$, as described above.

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

Output Format

Output one integer per line, representing the maximum total amount of red envelopes.

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

113

见附件中的 2.in。

见附件中的 2.ans。

见附件中的 3.in。

见附件中的 3.ans。

Hint

[Sample Explanation #1]

The optimal plan is to make dish $1$ and dish $2$. If so, although the $2$-nd guest will angrily leave, the total amount of red envelopes left by the other two guests is the largest.

[Subtasks]

This problem has 4 subtasks:

• Subtask 1 (20 points) has the special constraint: $n\leq 10, m\leq 2000$.
• Subtask 2 (20 points) has the special constraint: $n\leq 14$.
• Subtask 3 (20 points) has the special constraint: for each friend, the indices of the dishes he dislikes form an 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 \left[l,r\right]$.
• Subtask 4 (40 points) has no special constraints.

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

[Note]

For some test points, the input size is large. Please pay attention to the IO efficiency of your program.

Problem License

From Tsinghua University’s 2021 National Outstanding High School Students Informatics Experience Camp (THUSC 2021).

In the following, “this repository” refers to the official THUSC 2021 repository (https://gitlink.org.cn/thusaa/thusc2021).

1. Any organization or individual may use or repost the problems in this repository for free.
2. When using the problems in this repository, any organization or individual should keep it free and public. It is strictly forbidden to use these problems for profit or to add special access permissions to these problems.
3. If possible, please provide ways to obtain resources such as testdata, standard solutions, and solution write-ups when using the problems in this repository. Otherwise, please attach the address of this repository.
4. The Department of Computer Science, Tsinghua University, reserves all rights.

Translated by ChatGPT 5