题目描述

农夫约翰${N}$奶牛${(1 <= N <= 20)}$，方便标记${1...N}$与往常一样，正在准备十项全能${N}$不同的事件（所以也许它会 更好地称为 ${N-athlon }$而不是十项全能，传统上只有 ${10 }$个事件）.

牛${i }$的技能水平为${s_ij (1 <= s_ij <= 1000)}$在参加赛事 ${j }$时.每头奶牛必须参加一个且只有一个项目，并且每个项目 都必须有一些奶牛参加.

所有奶牛的总分是它们参加比赛的技能水平的总和.

但是，如果他们特别印象深刻，赛事评委也可以给予奖励积分.有${B}$奖金${(1 <= B <= 20）}$法官可以给出的.奖金 ${i }$包含三个部分：

如果奶牛至少获得${P_i(1 <= P_i <= 40,000)}$为了第一${Ki?}$括仅涉及这些事件的其他奖金），他们将获得额外的${A_i(1 <= A_i <= 1000)}$

例如，让我们考虑${N = 3}$具有以下技能的奶牛：

E V E N T
| 1 | 2 | 3
--+---+---+--
C  1 | 5 | 1 | 7
--+---+---+--
O  2 | 2 | 2 | 4
--+---+---+--
W  3 | 4 | 2 | 1

例如，如果奶牛 ${1 }$参加活动 ${3，}$她将为团队赢得 ${7 }$分.

假设评委提供奖金（${B = 1}$），如果奶牛在前两个项目中得分至少为 ${7 }$分，他们将获得额外的 ${6 }$分.

在这里，最佳分配是将奶牛 ${1 }$分配给事件 ${1，}$将奶牛 ${2 }$分配给事件 ${3，}$将奶牛 ${3 }$分配给事件 ${2.}$

对于前两个事件，奶牛 ${1 }$将获得 ${5 }$分，奶牛 ${3 }$将获得 ${2 }$分，给他们 ${7 }$分，这足 以满足奖励${1.}$

因此，他们得分的总分将是${5+2+4+6=17.}$

请帮助决定奶牛应该尝试哪些项目来最大化它们的总分.

输入格式

第 ${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}$。

输出格式

第 ${1 }$行：奶牛可以获得的最大积分，包括奖金.

样例

输入样例

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

输出样例

17

提示

奶牛 ${1 }$将执行事件 ${1，}$奶牛 ${3 }$将执行事件 ${2，}$奶牛 ${2 }$将执行事件 ${3}$。