Maximizing Red Packet Gifts

Emiya is a talented high school cook who can prepare (m) different dishes. One day, Yaz, Zid, and their (n) friends come over to visit. Although Yaz and Zid will eat anything, the friends are quite picky.

For the (i)-th friend and the (j)-th dish, an integer (a_{i,j}) (with (a_{i,j} \geq -1)) represents the friend’s attitude towards that dish:

• If (a_{i,j} \geq 0), then the friend does not dislike the dish. If the dish is served and none of the other served dishes is hated (i.e. none has (a_{i,j} = -1)), the friend will give Emiya a red packet of (a_{i,j}) yuan as a token of gratitude.

• If (a_{i,j} = -1), then the friend dislikes the dish. If such a dish is served, the friend becomes very angry and leaves immediately, and will not give any red packet.

Your task is to help Emiya select a subset of dishes to serve (the subset can be any nonempty set of the (m) dishes) so that the total amount of red packets received is maximized. Output this maximum total amount.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of friends (excluding Yaz and Zid) and the number of dishes, respectively.

Each of the following \(n\) lines contains \(m\) space-separated integers. The \(j\)-th integer in the \(i\)-th line is \(a_{i,j}\), indicating the \(i\)-th friend’s attitude towards the \(j\)-th dish.

outputFormat

Output a single integer, which is the maximum total red packet amount Emiya can receive by selecting an optimal subset of dishes.

sample

3 4
1 -1 2 3
0 5 -1 2
2 2 2 2

7