Description

OceatCat在学完C++语法后觉得这些都太简单了，他觉得自己学的这么快简直就是天才，随后他开始到处炫耀。

但是一位World Final选手看到了这句话并给了OceanCat一道题，很显然OceanCat是一定做不出来的，所以OceanCat决定要去学习更难的东西，他决定从数论开始学起(，然而他并没有相关书籍，他想要从网上尽可能多的去买一些数论相关的书籍进行研究，但是他现在身无分文。

OceanCat想了想自己能做点什么去赚钱吗？好像他什么也不会，所以他决定用最简单的方法--卖废品进行赚钱买书。他赚到的钱会尽可能多地去购买书籍，如果在购买书籍后会有剩余的钱，那么自然是剩的越多越好，毕竟可以自由支配了(。

现在OceanCat有n种废品，每种废品有m件，废品回收站看他很可怜决定在这n*m件废品中收走至多m件，对于第i种物品，如果我们卖出去了j件，那么我们会得到w~i,j~ 的收益。OceanCat的算数能力很差，所以他他向你寻求帮助。而你因为他找你进行帮助太过频繁而决定只告诉他最多能够得到多少收益，剩下的怎么组合让他自己想去吧！

所以，请你告诉他能够得到的最大收益是多少？

Input Format

第一行两个整数n, m(1≤n,m≤500)，含义如题目所示。

接下来n行，每行给出m个整数表示 $w​_{i,1}​,\cdots,w_{i,m} (1≤w_{​i,j}​≤1000)$

Output Format

一个整数，表示你的答案。

5 5
5 1 1 5 2
2 7 8 2 4
4 1 6 9 1
8 10 10 6 1
8 7 2 8 10​

28​

Hint

关于为什么对于某件废品卖的多反而会出现收益少的情况，或许是因为该物品与自身发生了一定的反应导致生成了其他奇怪的物质，而这里的收益自然就会给的是那个奇怪的物质的价值(

Source

动态规划 签到