Description

题目大意

约翰有 $N$ 头奶牛，组成了一支队伍参加全能比赛。

比赛一共有 $N$ 项，按照顺序依次进行。每头奶牛必须参加一项比赛，每项比赛也必须有一头奶牛参加。

每头奶牛都可以胜任每一项比赛，但得分不一样。如果第 $i$ 头奶牛参加第 $j$ 项比赛，在比赛结束的时候，可以为团体总分增加 $S_{i,j}$。

除了上述获得分数的方法之外，还有 $B$ 种奖励分。获得奖励的方法是在前几项比赛里获得足够的分数。

具体来说，第 $i$ 项奖励会在第 $K_i$ 项比赛结束的时候检查，如果当时的总分大于或等于 $P_i$，奶牛们就可以立即获得额外的 $A_i$ 分。

如果有多项奖励在同一时刻检查，奶牛可以自由安排检查和加分的顺序。

请问约翰应该如何安排奶牛参加比赛，才能让它们获得最高的分数？

Input Format

第 $1$ 行：两个整数 $N$ 和 $B$。

第 $2$ 行到第 $B+1$ 行：第 $i+1$ 行有三个整数 $K_i$，$P_i$ 和 $A_i$。

第 $B+2$ 行到第 $B+N+1$ 行：第 $i+B+1$ 行有 $N$ 个整数，代表 $S_{i,1}$ 到 $S_{i,N}$。

Output Format

单个整数，表示奶牛们可以获得的最大得分。

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

17

Hint

样例解释 #1

第一项比赛由第一头奶牛参加，第二项比赛由第三头奶牛参加，第三项比赛由第二头奶牛参加。

数据范围

对于所有数据，$1 \le N,B \le 20$，$1 \le K_i \le N$ ，$1 \le P_i \le 4 \times 10^4$，$1 \le A_i \le 10^3$，$1 \le S_{i,j} \le 10^3$。

translator：2018_RNG丶妖夢