题目描述

灵梦收集了 $n$ 个异变石，并把它们按顺序排成一个环，保证 $n$ 是奇数。

这些异变石一共有 $m$ 个不同的种类，第 $i$ 个异变石的种类我们用 $a_i$ 表示。

灵梦现在要从这 $n$ 个异变石中提取出异变之力，她会进行以下的操作直至环上只剩下一块异变石：

• 灵梦会选择在环上相邻的两块异变石，假设这两块异变石的种类分别为 $i$ , $j$ ,灵梦会从中提取出 $c_{i,j}$ 的异变之力，之后，这两块异变石的异变之力将会消失，于是灵梦将会把这两块石头从环上移除，这两块异变石两端的异变石将会相邻。

在灵梦进行最优操作的情况下，她最多能提取多少异变之力？注意，$c_{i,j}$ 可能是负数哦！

输入格式

输入第一行两个整数 $n$ , $m$ ,含义见题意，题目保证 $n$ 是奇数。 $(1 \leq m \leq n \leq 400)$

输入第二行 $n$ 个整数 $a_i$ ,第 $i$ 个整数表示第 $i$ 块异变石的种类。 $(1 \leq a_i \leq m)$

接下来 $m$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的数表示 $c_{i,j}$ ， $c_{i,j}$ 的含义见题意，题目保证有 $c_{i,j}=c_{j,i}$ 。 $(-10^9 \leq c_{i,j} \leq 10^9)$

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

5 3
1 2 1 2 3
2 -9 1
-9 3 4
1 4 6

输出 #1

6

说明与提示

对于样例 #1:

先选择异变石 $4$ , $5$ ,再选择异变石 $1$ , $3$ ,可以得到 $4+2=6$ 异变之力，可以证明，不存在使答案超过 $6$ 的操作序列。