OI题库

【题目描述】

农夫约翰的奶牛（1≤n≤20），总是方便的标记为1……N，或许应该叫N项全能，因为有N个不同的事件（通常有10个事件）。

牛i有一个s_ij的技能水平（1<=s_ij＜＝1000），是牛i在参与项目j时会得到的分数。每头奶牛必须且只能参加一个项目，每个事件必须有一些牛参加。

所有奶牛总得分为他们参加项目事件中的技能水平和。然而，项目的裁判如果有深刻印象，可以给出奖励分。评委可以给出B种奖励分（1≤B≤20）。奖励分i有三部分：如果奶牛在前k_i事件（包括这些事件其他牛的分数）获得了至少p_i（1< = p_i＜＝40000）分，他们将获得额外的a_i（1<=a_i<=1000）分（前k项触发的奖励积分不算到前k项的分数和，但算到之后的分数和中）。

例如，让我们考虑n = 3头牛技能水平如下：

	event
cow		1	2	3
	1	5	1	7
	2	2	2	4
	3	4	2	1

【输入格式】

第1行为N和B；

接下来有B行（2--B+1），其中第i+1行为 K_i, P_i,A_i；

再接下来有N行（B+2--B+1+N），其中第B+N+j行表示 s_j1...s_jN. 。

【输出格式】

输出只有一行，即牛得到的最大分数，包括奖励分。

【样例输入】

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

【样例输出】

17

【提示】

输出解释：

牛1参与项目1，牛2参与项目3，牛3参与项目2。

【来源】

在此键入