AT_pakencamp_2019_day3_c カラオケ

有一个由 $1, 2, \ldots, N$ 编号的 $N$ 名学生组成的小组，将要参加“全国统一卡拉OK大赛”。 在本次比赛中可以演唱的歌曲有 $M$ 首，分别为第 $1$ 首、第 $2$ 首，……，第 $M$ 首。编号为 $i$ 的学生演唱第 $j$ 首歌时，必定能获得 $A_{i, j}$ 分。 比赛的规则如下： - 从 $M$ 首歌中选择两首歌（分别记为 $T_1$ 和 $T_2$）。 - 每位学生都要演唱这两首歌。 - 每位学生的得分为他演唱这两首歌所得分数中的较高者。 - 小组的得分为所有学生得分的总和。 请你求出小组得分可能取得的最大值。

输入通过标准输入给出，格式如下： > $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}$

请输出小组得分可能取得的最大值，结果为整数。

### 限制条件 - $1 \leq N \leq 100$ - $2 \leq M \leq 100$ - $0 \leq A_{i, j} \leq 100\,000\,000$ - 输入均为整数 ### 部分得分 本题分为若干小题，若某小题的所有测试点均通过，则视为该小题通过。 提交代码的得分为通过的小题分数之和。 1. (10 分) $N = 1$，$M = 2$。 2. (25 分) $M = 2$。 3. (35 分) $N = 1$。 4. (30 分) 无额外限制。 ### 注意 **本题中的卡拉OK与普通卡拉OK不同，分数可能高达 $100\,000\,000$。** **此外，分数必为整数，不会出现 $314159.265$ 这样的非整数分数。** ### 样例解释 1 学生 $1$ 唱第 $1$ 首歌得 $80$ 分，唱第 $2$ 首歌得 $84$ 分。因此，该学生得分为 $84$ 分。由于小组只有 $1$ 人，所以小组得分为 $84$ 分。该输入样例满足小题 $1$ 的限制。 ### 样例解释 2 例如，该小组选择第 $1$ 首和第 $3$ 首歌： - 学生 $1$：第 $1$ 首歌得 $37$ 分，第 $3$ 首歌得 $70$ 分，得分为 $70$ 分。 - 学生 $2$：第 $1$ 首歌得 $85$ 分，第 $3$ 首歌得 $76$ 分，得分为 $85$ 分。 - 学生 $3$：第 $1$ 首歌得 $53$ 分，第 $3$ 首歌得 $95$ 分，得分为 $95$ 分。 因此，小组得分为 $70+85+95=250$ 分。没有办法让小组得分达到 $251$ 分或更高。 ### 样例解释 3 该输入样例满足小题 $2$ 的限制。 由 ChatGPT 4.1 翻译