BZPRO
#3446. [Usaco2014 Feb]Cow Decathlon
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
FJ有N(1 <= N <= 20)头奶牛，编号1至N。FJ提供N种不同的技能供奶牛们学习，每头奶牛只能学习一门技能，每门
技能都要有奶牛学习。 第i头奶牛学习第j门技能，FJ得到的分数S[i][j]，1<=S[i][j]<=1000。此外还有B(1 <= B
<= 20)个奖励，第i个奖励的格式是： Pi 、Ki 、Ai，表示的意义是：如果学习完前Ki门技能后的总得分（包括
额外的奖励得分）不少于Pi，那么FJ还会得到额外的Ai分。那么FJ应该如何安排奶牛学习技能，才能使得最后的总
得分最高？
输入格式
第一行，N和B。 接下来有B行，每行三个整数：Ki,Pi 、 Ai。
1 <= Pi <= 40000，1 <= Ai <= 1000。
接下来有N行N列的二维数组，表示S[i][j]。1 <= S[i][j] <= 1000。
输出格式
一个整数，最大得分。
样例
样例输入
3 1
2 7 6
5 1 7
2 2 4
4 2 1
样例输出
17
//奶牛1学习技能1，奶牛2学习技能3，奶牛3学习技能2。
数据范围与提示
BZPRO