TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2766
  • 题目
  • P2766【USACO 2014 February Gold】运动会
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    约翰有N(1 <= N <= 20)头奶牛,编号1到N。它们准备参加运动会,运动会共N个项目。
    i号奶牛从事第j项运动的能力为s_ij (1 <= s_ij <= 1000)。每头奶牛必须参加1项运动,且只能参加一个项目。每个项目都必须有奶牛参加。
    运动会的得分是每头奶牛参与项目对应的能力值的总和。但是,如果在比赛中表现得非常突出,比赛的裁判可以给出额外的奖励分。裁判共有B(1 <= B <= 20)次机会给出奖励分。获得第i次奖励分需满足条件:
    如果奶牛在前K_i个项目中获得了至少P_i分(包括K_i个项目中的奖励得分,1 <= P_i <= 40,000),它们将得到A_i分的奖励(1 <= A_i <= 1000)
    比如,有N=3只奶牛,它们的运动能力值如下表:

          运动项目
         | 1 | 2 | 3
       --+---+---+--
    奶 1 | 5 | 1 | 7
       --+---+---+--
    牛 2 | 2 | 2 | 4
       --+---+---+--
    们 3 | 4 | 2 | 1

    如上表所示,1号奶牛参加3号运动项目可以获得7分。

    假如奶牛在前两个项目中得分至少有7分,裁判就会提供一次奖励(B = 1),它们会获得6分的奖励分。
    一个合理的安排是1号奶牛参加项目1,2号奶牛参加项目3,3号奶牛参加项目2.这样,在前两个项目中,1号牛得5分,3号牛得2分,达到7分的要求,于是获得6分的加分。第3个项目由2号牛参加,得4分。总得分为5+2+6+4=17


    请帮助奶牛们安排参赛顺序,使得最后总得分最大。

    输入格式

    第一行,两个整数N和B
    接下来B行,每行三个整数K_i, P_i, A_i,代表一次奖励的条件
    接下来是一个N*N的矩阵,代表奶牛参与对应项目的能力值

    输出格式

    一个整数,表示奶牛能得到的最大得分

    样例输入

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

    样例输出

    17