题目描述

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

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

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

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

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

例如，让我们考虑$\red{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

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

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

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

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

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

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

输入格式

第 $\red{1 }$行：两个空格分隔的整数：$\red{N, B}$

第 $\red{2..B+1 }$行：第 $\red{i+1 }$行将包含奖励 $\red{i }$的信息，它是三个空格分隔的整数：$\red{K_i, P_i, A_i}$

第$\red{B+2..B+N+1 }$行：$\red{B+1+j }$行将包含有关奶牛 $\red{j }$在每个事件中的表现的信息.这将在$\red{N}$空格分隔的整数：$\red{s_j1...s_jN}$。

输出格式

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

样例

输入样例

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

输出样例

17

提示

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