问题 27162 --老师的工资

27162: 老师的工资

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

 不只是学生会在功课上偷懒,有时候老师也是一样的。对部分老师来说,如果不能够拿到足够的工资,他们的工作便不如被期望的那样努力。Fengzee给学校的校长提了一个建议,就是用合理的工资分配来使老师们工作的积极性达到最高。校长作为决策者,要考虑整个学校的m个老师,同时还要明白每年他只能在老师的工资上总共付出n万元钱(满足m,n为整数,且m

    Fengzee当然会写这个简单的程序,可是为了帮助你参加信息学竞赛,他想让你来练习一下。你的输入文件由两部分组成:第一部分有一行,用空格分隔,依次提供mn这两个整数;第二部分是一个m*n的矩阵,假设用a表示,那么矩阵中的元素a[i][j]的值是第i个老师在拿到j万元的年薪时的工作积极性,用一个整数表示,整数的规模不会很大。值得注意的是,对有些老师来说,拿过多的钱会增长惰性,使他们的工作积极性反而不如低工资的时候高。输出文件只有一行,包含一个整数p,表示最佳分配方案下的总积极性。答案正确并不超过时限是获得测试数据全部得分的充分必要条件。

样例输入

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


来源

 

[提交][状态]