#P3446. [Usaco2014 Feb]Cow Decathlon

    ID: 2646 传统题 1000ms 512MiB 尝试: 137 已通过: 73 难度: 5 上传者: 标签>难度分类普及+/提高-动态规划子集 DP贪心排序贪心位运算位计数支配关系CF1800Gold

[Usaco2014 Feb]Cow Decathlon

[USACO14FEB] Cow Decathlon G

题目描述

农夫约翰有 NN 头奶牛,要参加按 11 到 NN 顺序举行的 NN 项比赛。每头奶牛必须参加一项比赛,每项比赛恰好由一头奶牛参加。奶牛 ii 参加第 jj 项比赛,可以为队伍获得 Si,jS_{i,j} 分。

评委还设置了 BB 项奖励。对于第 ii 项奖励,如果结束前 KiK_i 项比赛后,累计得到的分数至少为 PiP_i,队伍就额外获得 AiA_i 分。累计分数包含已经获得的奖励。同一项比赛结束时,刚获得的奖励可以提高累计分数,使队伍达到该时刻其他奖励的门槛。每项奖励至多领取一次。

求安排奶牛参赛所能得到的最高总分。

输入格式

第一行包含两个整数 N,BN,B,1≤N,B≤201\le N,B\le 20。

接下来 BB 行。第 ii 行包含三个整数 Ki,Pi,AiK_i,P_i,A_i,其中 1≤Ki≤N1\le K_i\le N,1≤Pi≤400001\le P_i\le 40000,1≤Ai≤10001\le A_i\le 1000。

接下来 NN 行,每行包含 NN 个整数。第 ii 行第 jj 个数为 Si,jS_{i,j},1≤Si,j≤10001\le S_{i,j}\le 1000。

输出格式

输出一个整数,表示包含奖励的最高总分。

样例 #1

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

样例解释

三场比赛依次由奶牛 1,3,21,3,2 参加,分别得到 5,2,45,2,4 分。前两场共得 77 分,触发额外的 66 分,因此总分为 5+2+4+6=175+2+4+6=17。