Problem Description

A group consisting of $N$ students numbered $1, 2, ..., N$ will participate in the "National Unified Karaoke Contest".

There are $M$ songs that can be sung in this contest: Song $1$, Song $2$, ..., Song $M$. Additionally, when student $i$ sings song $j$, they will always score $A_{i, j}$ points.

The rules of the contest are as follows:

• Choose 2 songs from the $M$ songs (let them be $T_1$ and $T_2$).
• Each student will sing both Song $T_1$ and Song $T_2$.
• Each student's score will be the higher of the two scores they get from the songs they sang.
• The group's score will be the sum of the scores of students $1, 2, ..., N$.

Find the maximum possible score for the group.

Input Format

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

$N$ $M$ $A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ ... $A_{1, M}$ $A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ ... $A_{2, M}$ $A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ ... $A_{3, M}$ : $A_{N, 1}$ $A_{N, 2}$ $A_{N, 3}$ ... $A_{N, M}$

Output Format

Output the maximum possible score for the group as an integer.

Sample Input and Output

Sample Input #1

1 2
80 84

Sample Output #1

84

Sample Input #2

3 4
37 29 70 41
85 69 76 50
53 10 95 100

Sample Output #2

250

Sample Input #3

8 2
31000000 41000000
59000000 26000000
53000000 58000000
97000000 93000000
23000000 84000000
62000000 64000000
33000000 83000000
27000000 95000000

Sample Output #3

581000000

Notes/Hints

Constraints

• $1 \leq N \leq 100$
• $2 \leq M \leq 100$
• $0 \leq A_{i, j} \leq 100,000,000$
• All inputs are integers

Partial Points

This problem is divided into several sub-tasks, and you will be considered to have solved a sub-task if you correctly solve all test cases for that sub-task. The score for your submitted source code will be the sum of the points for the sub-tasks you solved.

1. (10 points) $N = 1$, $M = 2$.
2. (25 points) $M = 2$.
3. (35 points) $N = 1$.
4. (30 points) No additional constraints.

Note

The karaoke in this problem is different from the usual karaoke, as it can score up to $100,000,000$ points.
Also, the score is always an integer, and scores like $314159.265$ points are not possible.

Sample Explanation 1

Student $1$'s score for Song $1$ is $80$ points, and for Song $2$ is $84$ points. Therefore, student $1$'s score is $84$ points. Since there is only one student in the group, the group's score is $84$ points. This input example satisfies the constraints of sub-task $1$.

Sample Explanation 2

For example, if the group sings Song $1$ and Song $3$:
- Student $1$: Score for Song $1$ is $37$ points, and for Song $3$ is $70$ points. Therefore, this student's score is $70$ points.
- Student $2$: Score for Song $1$ is $85$ points, and for Song $3$ is $76$ points. Therefore, this student's score is $85$ points.
- Student $3$: Score for Song $1$ is $53$ points, and for Song $3$ is $95$ points. Therefore, this student's score is $95$ points.
Thus, the group's score is $70 + 85 + 95 = 250$ points. There is no way to make the group's score $251$ points or higher.

Sample Explanation 3

This input example satisfies the constraints of sub-task $2$.

见题面 Input 部分

见题面 Output 部分