约翰有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的矩阵，代表奶牛参与对应项目的能力值

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