New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2004: 年夜饭

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：56 通过：18
提交提交记录统计

题目描述

除夕晚上，Alice和Bob以及亲戚们围着一张超大的圆桌吃年夜饭。
因为桌子太大，每份菜都会被拆成若干份上桌。
因为众人的口味不一样，将一盘菜摆在不同人的面前会获得不同的好感度。
为了拿到更多的压岁钱，Alice和Bob要尽可能使众人的好感度总和最高
希望你帮忙计算这个最大值。有以下几点需要注意：
        1、 一份菜可以拆分成任意份，每个人的面前可以放任意份菜。
        2、 获得的好感度只跟放没放有关，和拆分份数、已经放了几份菜无关。
        3、因为大家都不愿意一直吃同一份菜，同一种菜不能相邻摆放。圆桌上，第1位客人和第N位客人也是相邻的。

输入格式

第一行是菜的个数N(1<=N<=1000)和客人总数M(1<=M<=1000)。

接下来N行每行包含M个整数，表示第i位客人对该菜的好感度为Ai(1<=Ai<=10000)。

输出格式

输出一个数字，即好感度总和最大值。

输入样例 复制 

2 5
2 3 2 4 7
1 2 3 1 5

输出样例 复制 

18

数据范围与提示

第一份菜应该放在2号和5号客人面前。
第二份菜应该放在3号和5号客人面前。