题目描述

众所周知，许多溶液之间是互不相溶的，将它们混合在一起便是乳浊液，久置后便会形成分层现象。分层的时候呢，自然是密度大的会在下层，比如四氯化碳会在水的下层，而苯则会在水的上层。

材料科学与化学工程学院的侯德榜同学闲来无事就喜欢把溶液混合在一起，形成各种美丽的分层效果。现在他手头有N种溶液，而每种溶液都有一种颜色，他可以从中选取若干种(至少一种)溶液混合，来达到最美丽的效果。为了标度美丽的程度，他便定义了一个BL(beautiful liquid)值的概念：
1、每种颜色都有一个BL值；
2、每两种颜色也会对应一个BL值，表示这两种颜色相邻时的美丽程度；
3、整个分层浊液的BL值=两两相邻颜色的BL值之和+所有溶液颜色的BL值之和。

他现在调制出了很多种BL值很高的分层效果，但是呢，他无法确定这是不是最好的效果，如果你能帮助它搞定这个问题，想必他就会觉得算法很有意思，从而来参加明年的校赛了。

输入要求

第1行两个整数N,M，分别表示溶液的种数以及颜色的种数。(1<=N<=1000,1<=M<=100)
第2行N个整数C[1]~C[N]，C[i]表示第i种溶液的颜色编号是什么。溶液已经按照密度从大到小排好序了，没有密度相同的溶液。(1<=C[i]<=M)
第3行M个整数BL1[1]~BL1[N]，BL1[i]表示第i种颜色的BL值是什么。(-1000<=BL1[i]<=1000)
接下来是一个M*M的矩阵BL2[][]，Bl2[i][j]表示第i种颜色与第j种颜色相邻时的BL值。(-1000<=BL2[i][j]<=1000，BL2[i][i]=-BL1[i]，BL2[i][j]=BL2[j][i],1<=i,j<=M)

输出要求

输出一个整数，表示可以获得的最高BL值。

输入样例

3 2
1 2 2
-1 2
1 3
3 -2

输出样例

4

提示

BL(1)=BL1[1]=-1;
BL(2)=BL(3)=BL1[2]=2;
BL(1,2)=BL(1,3)=BL1[1]+BL1[2]+BL2[1][2]=4;
BL(2,3)=BL1[2]+BL1[2]+BL2[2][2]=2;
BL(1,2,3)=BL1[1]+BL1[2]+BL1[2]+BL2[1][2]+BL2[2][2]=4;
因此选取1、2号溶液或者选取1、3号溶液或者选取1、2、3号溶液都可以达到最大值4。

来源

信息学院第五届程序设计大赛