配点: 100 点
問題文
1, 2, ..., N 编号为 N 一批学生将参加“全国卡拉OK大赛”。
本次比赛可以演唱的歌曲有 1,曲 2,...,曲 M 可以得到第 M 有一首歌。另外,数量 i 学生唱歌 每当你唱 j 时, A_{i, j} 拿分。
现将比赛规则如下。
- M 摘自歌曲 2 选择一首歌曲。 (分别 T_1 和 按字典顺序比较 T_2 。 )
- 每个学生唱一首歌。 T_1 和歌曲 唱两个 T_2 。
- 每个学生的分数基于学生演唱的歌曲数量。 2 分数将是两首歌曲中较高的一个。
- 小组分数为 这是 1, 2, ..., N 的总分。
此时,找出该组得分的最大可能值。
制約
- 1 \leq N \leq 100
- 2 \leq M \leq 100
- 0 \leq A_{i, j} \leq 100 \ 000 \ 000
- 所有输入均为整数
部分点
该问题分为多个子任务,如果您正确回答了该子任务中的所有测试用例,则视为您正确回答了该子任务。
提交的源代码的分数是您正确回答的子作业分数的总和。
- (10 点) N = 1,M = 2.
- (25 点) M = 2.
- (35 点) N = 1.
- (30 分) 没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
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}
出力
请以整数形式输出该组的最大可能得分。
注意
此问题中的卡拉 OK 与普通卡拉 OK 不同,
可以给予100 \ 000 \ 000 点。
另外,分数始终是整数,314159.265 非整数的点永远不会出现。
入力例 1
1 2 80 84
出力例 1
84
生徒 1 歌曲 1 的分数是 80 点,曲 2 的分数是 84 点。因此,学生 1 的分数是
可以看出,它位于 84 。
此外,该小组还 1 由于只有 1 名学生,该组的分数为 84 。
此输入示例是一个小任务。 它满足 1 约束。
入力例 2
3 4 37 29 70 41 85 69 76 50 53 10 95 100
出力例 2
250
例如,如果该组 如果你唱 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
8 2 31000000 41000000 59000000 26000000 53000000 58000000 97000000 93000000 23000000 84000000 62000000 64000000 33000000 83000000 27000000 95000000
出力例 3
581000000
这个输入示例是 不满足条件 2 约束。