#363. 程序猿的工资

程序猿的工资

题目描述

在A公司有一堆程序猿,程序猿们如果不能够拿到足够的薪水,他们便会变得非常懒,不想干活,甚至对项目经理破口大骂。但是我们可以通过合理的薪水分配来使程序猿们工作更加积极。于是公司的老板找到了你来帮忙,每年老板只能总共付出 mm 万元钱(假设老板心地善良,为员工着想,mm 万元必须全部分配给每一个员工),且要考虑 nn 个程序猿的每一名(满足 m,nm,n 为正整数)。

每个程序猿一月得到的钱都是整万元,每一个程序猿在每一种不同的薪水数额下,工作的效率是不同的。现在让你来分配薪水,使得总积极性最高。

输入格式

第一行两个整数,分别是 nnmm

接下来的 nn 行每行包含 mm 个整数,构成一个 nmn \cdot m 的矩阵

矩阵的第 ii 行第 jj 列的数 aija_{ij} 表示第 ii 个程序猿在拿到 jj 万元工资时的积极性。

输出格式

一行一个整数,表示在支出等于 mm 时的积极性的最大值。

样例

样例输入

2 3
1 2 3
2 3 4

样例输出

4

数据范围与提示

数据范围

对于 30%30\% 的数据 ,满足 1m,n101 \le m, n \le 10
对于 70%70\% 的数据 ,满足 1m,n601 \le m, n \le 60
对于 100%100\% 的数据,满足 1m,n1001 \le m, n \le 100

样例解释

分配给第一个程序猿 22 万元的工资,获得积极度 22

分配给第二个程序猿 11 万元的工资,获得积极度 22

总共支出 33 万元,获得积极度 44

显然,44 是在支出满足等于 33 万元的情况下的最大积极度