题面翻译

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

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

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

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

如果有多项奖励在同一时刻检查，奶牛可以自由安排检查和加分的顺序。请问约翰应该如何安排奶牛参加比赛，才能让它们获得最高的分数？

输入格式

第一行：两个整数 $N$ 和 $B$，$1\le N\le 20,1\le B\le 20$。

第二行到第 $B+1$ 行：第 $i+1$ 行有三个整数 $K_i,P_i,A_i(1\le Ki\le N ,1\le Pi\le 40000 , 1\le Ai\le 1000)$。

第 $B+2$ 行到第 $B+N+1$ 行：第 $i+B+1$ 行有 $N$ 个整数，代表 $S_{i,1}\cdots S_{i,N}$，对每个 $1\le j\le N , 1\le S_{i,j}\le 1000$。

输出格式

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

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

17

提示

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