题目内容

命名实体识别、词性标注和文本分词都可以看成序列标注：句子里的每个词要标上一个标签。例如句子

OpenAI develops powerful models

一种标注结果是

ORG  O  O  O

线性链条件随机场在给出最终标签序列时，同时使用两类分数。一类是某个位置本身适不适合某个标签，另一类是相邻两个标签接在一起合不合适。例如标签 I-PER 通常不紧挨在 O 后面。模型已经训练完成，并给出了下面这些分数。请根据这些分数，为整条序列选出总分最高的标签序列。

序列长度为 $N$，标签有 $K$ 种，编号为 $1, 2, \ldots, K$。第 $i$ 个位置选择标签 $j$ 的局部得分是 $E_{i,j}$。上一个位置的标签为 $a$、当前位置的标签为 $b$ 时，额外得到转移得分 $T_{a,b}$。转移得分可以为正、为 $0$，也可以为负。

标签序列 $y_1, y_2, \ldots, y_N$（$1 \le y_i \le K$）的总分为每个位置的局部得分，再加上每对相邻标签的转移得分：

$\sum_{i=1}^{N} E_{i,y_i} + \sum_{i=1}^{N-1} T_{y_i, y_{i+1}}$

第一个位置前面没有标签，不加起始转移。最后一个位置后面没有标签，不加结束转移。$N = 1$ 时总分只含局部得分。

某个位置上局部得分最高的标签，接到前一个标签上时转移得分可能很低，整条序列的总分就会低于另一条局部得分略低的序列。求所有标签序列中的最大总分。只输出这个整数，不输出标签序列。

输入描述

第一行两个整数 $N$、$K$。

接下来 $N$ 行，每行 $K$ 个整数。第 $i$ 行第 $j$ 个数是 $E_{i,j}$。

接下来 $K$ 行，每行 $K$ 个整数。第 $a$ 行第 $b$ 个数是 $T_{a,b}$。

约束

$1 \le N \le 10000$

$1 \le K \le 30$

$-10^6 \le E_{i,j}, T_{a,b} \le 10^6$

答案在 $64$ 位有符号整数范围内。

输出描述

输出一个整数，表示总分的最大值。

样例1

输入

4 3
5 1 0
2 4 1
1 3 5
4 2 3
0 2 -1
1 0 2
-2 1 0

输出

21

说明

标签序列 $1, 2, 3, 2$ 的位置得分为 $E_{1,1} + E_{2,2} + E_{3,3} + E_{4,2} = 5 + 4 + 5 + 2 = 16$。

转移得分为 $T_{1,2} + T_{2,3} + T_{3,2} = 2 + 2 + 1 = 5$。

总分为 $16 + 5 = 21$。

样例2

输入

2 2
5 4
0 1
-10 0
3 0

输出

7

说明

四条序列的总分：

• $1, 1$：$5 + 0 + T_{1,1} = 5 + 0 + (-10) = -5$
• $1, 2$：$5 + 1 + T_{1,2} = 6 + 0 = 6$
• $2, 1$：$4 + 0 + T_{2,1} = 4 + 3 = 7$
• $2, 2$：$4 + 1 + T_{2,2} = 5 + 0 = 5$

最大值为 $7$。