1361: 方格取数
Memory Limit：1024 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
小明在玩一个取数字的游戏
有一个n*m的网格，每一个网格都有一个数字$a_{i,j}$
游戏规则如下：
1.每行从第一个数字开始选，且必须连着选
2.每一行选的数字之和要大于上一行的数字之和，第一行没有这个限制条件
3.你可以从任意一行开始选，直到不能选为止
4.你的得分为选中的所有数字之和
小明想知道，对于给定的一个局面，他能获得的最大得分是多少？请你告诉他这个最大值
例如：
最优的策略就是第一行全部选上，这一行选的数字和为51，接着第二行全选上，这一行的数字和为71。第三行无法选。总得分为122
可以保证不会有其他的方法使得得分大于122
例如第一行选前3个，该行总和31，第二行选前两个，该行总和为37，第三行全选，该行总和为43。总得分为111
all $0<a_{i,j}\leq1000$
40分 : $n,m\leq200$
80分：$n,m\leq1000$
100分：$n,m\leq6000$
如果你需要80以上的分数请使用该代码进行读入：https://www.luogu.com.cn/paste/aao9hd2u
tip:
读入数据量超过1e5，则需要使用c语言的scanf或则使用关闭流通步后的cin，数据量接近1e7则需要使用快速读入
本题的数据量为n*m
有一个n*m的网格，每一个网格都有一个数字$a_{i,j}$
游戏规则如下：
1.每行从第一个数字开始选，且必须连着选
2.每一行选的数字之和要大于上一行的数字之和，第一行没有这个限制条件
3.你可以从任意一行开始选，直到不能选为止
4.你的得分为选中的所有数字之和
小明想知道，对于给定的一个局面，他能获得的最大得分是多少？请你告诉他这个最大值
例如：
最优的策略就是第一行全部选上，这一行选的数字和为51，接着第二行全选上，这一行的数字和为71。第三行无法选。总得分为122
可以保证不会有其他的方法使得得分大于122
例如第一行选前3个，该行总和31，第二行选前两个，该行总和为37，第三行全选，该行总和为43。总得分为111
all $0<a_{i,j}\leq1000$
40分 : $n,m\leq200$
80分：$n,m\leq1000$
100分：$n,m\leq6000$
如果你需要80以上的分数请使用该代码进行读入：https://www.luogu.com.cn/paste/aao9hd2u
tip:
读入数据量超过1e5，则需要使用c语言的scanf或则使用关闭流通步后的cin，数据量接近1e7则需要使用快速读入
本题的数据量为n*m
Input
第一个行，两个正整数n,m,分别表示网格的行和列
接下来n行，每行有m个正整数
接下来n行，每行有m个正整数
Output
一个正整数，表示最大得分
Sample Input Copy
3 4
4 12 15 20
20 17 19 15
8 11 20 4Sample Output Copy
122