810. 老师的工资

【问题描述】

不只是学生会在功课上偷懒，有时候老师也是一样的。对部分老师来说，如果不能够拿到足够的工资，他们的工作便不如被期望的那样努力。Fengzee给学校的校长提了一个建议，就是用合理的工资分配来使老师们工作的积极性达到最高。校长作为决策者，要考虑整个学校的m个老师，同时还要明白每年他只能在老师的工资上总共付出n万元钱（满足m,n为整数，且m<=n）。每个老师一年得到的钱都是整万元，如果认为给某个老师发工资比较亏本，校长可以决定辞退这名老师，同时不必支付任何金钱。在某些极端情况下，甚至可以把n万元钱全部给1名老师。经过一段时间的观察，校长发现，每一个老师在每一种工资数额下，工作的积极性是不同的。现在校长要求这个建议的提出者Fengzee写一个程序，来求出在一年中校长全部利用且只利用这n万元钱的情况下，老师们最佳的总积极性。总积极性被认为是每个老师的工作积极性的和。

Fengzee当然会写这个简单的程序，可是为了帮助你参加信息学竞赛，他想让你来练习一下。

【输入格式】

>第一行，用空格分隔的两个整数m和n；

接下来m行，每行有n个用空格隔开的整数，其中第i行第j列的数字表示第i个老师在拿到j万元的年薪时的工作积极性。

整数的规模不会很大。值得注意的是，对有些老师来说，拿过多的钱会增长惰性，使他们的工作积极性反而不如低工资的时候高。

【输出格式】

有一行，包含一个整数，表示最佳分配方案下的总积极性。

【输入样例】

5 10
30 40 60 80 100 110 120 100 90 80
20 50 80 100 120 130 133 134 135 136
20 60 70 90 140 160 180 190 210 220
30 50 70 90 110 130 150 170 190 210
40 55 100 130 135 140 145 150 155 160

【输出样例】

300

【数据规模】

1<=m<=15, 2<=n<=30