Home Web Board ProblemSet Standing Status Statistics
1.该OJ由于交换空间受限,暂不不支持万能头文件:bits/stdc++.h!!! 2.该OJ如果是长整型的话,C的输入输出请使用%lld!!!
Problem B: 来自二次元小姐姐初音未来的温暖

Problem B: 来自二次元小姐姐初音未来的温暖

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 2
[Submit][Status][Web Board]

Description

初音未来是一个流行的虚拟歌手。在日本和中国都很受欢迎。它是一个计算机软件,允许你使用声乐包自己编写一首歌曲。
今天你要组合一首歌,这只是一个音符序列。包装中只有不同的笔记。而且你想用n个音符制作一首歌曲。而且,你知道有一个系统来评估一首歌曲的美丽度。对于每两个连续的笔记a和b,如果b在a之后,则这两个音符的美丽度被评估为score(a,b)。所以一首歌曲的总美丽度由音符a 1,a 2,...组成。 。 。 ,an,的得分(ai,a i + 1)的总和(1≤i≤n-1)。现在,你发现在某些位置,音符必须是一些特定的,但在其他位置,你可以决定使用什么音符。你想要最大化你的歌曲的美丽。你最大的美丽度是多少?

Input

第一行包含整数T(T≤20),表示测试用例的数量。
对于每个测试用例,如上所述,第一行包含两个整数n(1≤n≤100)和m(1≤m≤50)。然后m行跟随,每个由m个空格分隔的整数组成,第i行的第j个整数用于得分(i,j)(0≤score(i,j)≤100)。下一行包含n个整数,a 1,a 2,...。 。 。 ,n(-1≤ai≤m,a i≠0),其中正整数代表您不能改变的音符,而负整数是可以用任意音符替换的。笔记的名称从1到m.

Output

对于每个测试用例,将答案输出一行。

Sample Input

2
5 3
83 86 77
15 93 35
86 92 49
3 3 3 1 2
10 5
36 11 68 67 29
82 30 62 23 67
35 29 2 22 58
69 67 93 56 11
42 29 73 21 19
-1 -1 5 -1 4 -1 -1 -1 4 -1

Sample Output

270
625

HINT

[Submit][Status][Web Board]