### 问题描述 小齐有 $N$ 头奶牛，编号从 $1$ 到 $N$，它们正在为一个包含 $N$ 个不同项目的多项式运动（可能更好称为 $N$ 项运动，因为传统上十项运动是有十个项目的）做准备。 奶牛 $i$ 在参加第 $j$ 项运动时的技能水平为 $s_{ij}$（$1 \leq s_{ij} \leq 1000$）。每头奶牛必须参加且只能参加一个项目，每个项目必须有奶牛参加。 所有奶牛的总分是它们在参加的项目中技能水平之和。然而，裁判也可以根据表现给予额外的奖励分数。共有 $B$ 个奖励（$1 \leq B \leq 20$）供裁判分发。第 $i$ 个奖励有三个部分：如果奶牛在前 $K_i$ 个项目中至少获得 $P_i$ 分（包括其他仅涉及这些项目的奖励），则它们将获得额外的 $A_i$ 分（$1 \leq P_i \leq 40,000$，$1 \leq A_i \leq 1000$）。 请帮助决定奶牛应该尝试哪些项目，以最大化它们的总分。 ### 输入格式 第 $1$ 行：两个由空格分隔的整数：$N, B$ 第 $2$ 行到第 $B+1$ 行：第 $i+1$ 行包含有关奖励 $i$ 的三个由空格分隔的整数：$K_i, P_i, A_i$ 第 $B+2$ 行到第 $B+N+1$ 行：第 $B+1+j$ 行包含有关奶牛 $j$ 将在每个项目中的表现。这将在 $N$ 个由空格分隔的整数中给出：$s_{j1}...s_{jN}$。 ### 输出格式 奶牛们可以获得的最大分数，包括奖励。 ### 样例输入 ``` 3 1 2 7 6 5 1 7 2 2 4 4 2 1 ``` ### 样例输出 ``` 17 ``` ### 评测数据规模 $1 \leq N, B \leq 20，1 \leq K_i \leq N，1 \leq P_i \leq 40,000，1 \leq A_i \leq 1000，1 \leq s_{ij} \leq 1000$。