#P3446. [Usaco2014 Feb]Cow Decathlon
[Usaco2014 Feb]Cow Decathlon
[USACO14FEB] Cow Decathlon G
题目描述
农夫约翰有 头奶牛,要参加按 到 顺序举行的 项比赛。每头奶牛必须参加一项比赛,每项比赛恰好由一头奶牛参加。奶牛 参加第 项比赛,可以为队伍获得 分。
评委还设置了 项奖励。对于第 项奖励,如果结束前 项比赛后,累计得到的分数至少为 ,队伍就额外获得 分。累计分数包含已经获得的奖励。同一项比赛结束时,刚获得的奖励可以提高累计分数,使队伍达到该时刻其他奖励的门槛。每项奖励至多领取一次。
求安排奶牛参赛所能得到的最高总分。
输入格式
第一行包含两个整数 ,。
接下来 行。第 行包含三个整数 ,其中 ,,。
接下来 行,每行包含 个整数。第 行第 个数为 ,。
输出格式
输出一个整数,表示包含奖励的最高总分。
样例 #1
3 1
2 7 6
5 1 7
2 2 4
4 2 1
17
样例解释
三场比赛依次由奶牛 参加,分别得到 分。前两场共得 分,触发额外的 分,因此总分为 。