Problem Background

Due to the large scale of the test data for this problem, only a portion of the test data will be evaluated. The remaining test data can be submitted for testing at U412486.

Problem Description

Emiya is a high school student skilled in cooking, capable of preparing $m$ different dishes. One day, Yaz, Zid, and their $n$ friends visit his home, and Emiya needs to prepare some dishes to entertain them.

Yaz and Zid eat anything, but their friends are picky eaters. Specifically, we use integers $a_{i,j} \geq -1$ to represent the attitude of the $i$-th friend towards 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, he will leave a red envelope with $a_{i,j}$ yuan 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, he will become very angry and leave immediately. This means he will not leave a red envelope for any dish.

Emiya is good at cooking but not at calculations. Please help Emiya select several dishes to maximize the total amount of red envelopes he receives. For convenience, you only need to output this maximum total amount.

Input Format

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

From the second to the $(n+1)$-th line, each line contains $m$ integers: the $(i+1)$-th line's $j$-th integer is $a_{i,j}$, as described in the problem.

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

Output Format

A single line containing one integer, representing the maximum total amount of red envelopes.

Sample Input and Output

Sample Input #1

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

Sample Output #1

113

Sample Input #2

See the attached file 2.in.

Sample Output #2

See the attached file 2.ans.

Sample Input #3

See the attached file 3.in.

Sample Output #3

See the attached file 3.ans.

Notes

[Sample Explanation #1]

The optimal solution is to prepare the 1st and 2nd dishes. Although the 2nd guest will leave angrily, the total amount of red envelopes left by the other two guests is maximized.

[Subtasks]

This problem is divided into 4 subtasks:

• Subtask 1 (20 points): Special restriction $n \leq 10, m \leq 2000$;
• Subtask 2 (20 points): Special restriction $n \leq 14$;
• Subtask 3 (20 points): Each friend's disliked dishes form a range, i.e., 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 restrictions.

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

[Hints]

Some test cases have large input sizes, please pay attention to the IO efficiency of your program.

Problem Usage Agreement

From the 2021 National Excellent Middle School Student Informatics Experience Camp (THUSC 2021) at Tsinghua University.

1. Any organization or individual may freely use or republish the problems in this repository;
2. Any organization or individual using the problems in this repository should do so without charge and publicly, and must not use these problems for profit or add special privileges to these problems;
3. If possible, please provide methods to obtain data, standard programs, and problem solutions when using the problems in this repository; otherwise, please attach the repository address.
4. The Department of Computer Science, Tsinghua University, reserves all rights.

见题面 Input 部分

见题面 Output 部分