UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3446. [Usaco2014 Feb]Cow Decathlon

Statistics 下载数据

Description

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应该如何安排奶牛学习技能,才能使得最后的总
得分最高?

Input

第一行,N和B。  接下来有B行,每行三个整数:Ki,Pi 、 Ai。
1 <= Pi <= 40000,1 <= Ai <= 1000。    
接下来有N行N列的二维数组,表示S[i][j]。1 <= S[i][j] <= 1000。 

Output

一个整数,最大得分。 

Sample Input

3 1
2 7 6
5 1 7
2 2 4
4 2 1

Sample Output

17
//奶牛1学习技能1,奶牛2学习技能3,奶牛3学习技能2。

Hint

Source

Gold