测试数据来自 system/1122

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　两个字符串的相似度就是对应字符之间的相似度总和。当然如果字符串不一样长，先在它们中插入一些空格变成一样长后，在计算对应字符之间的相似度总和。

　　现在给出字符之间的相似度表（包括空格与其他字符之间），然后编程计算两个字符串之间的最大相似度。

【输入格式】

　　第一行为 \(N\)，表示字符串是由前 \(N\) 个大写字母组成。
　　接下来的两两行，表示两个字符串，第一个整数是字符串的长度，第二个是字符串，超度均不超过 2000。
　　再接下来是 \(N\) 行 \(N\) 列的整数矩阵，其中第 \(i\) 行 \(j\) 列的整数 表示第 \(i\) 个大写字母与第 \(j\) 个大写字母的相似度，是一个[-100,100]之间的整数。
　　最后一行包含 \(N\) 个整数，第 \(i\) 个整数表示第 \(i\) 个大写字母与空格的相似度。

【输出格式】

　　输出两个字符串之间的最大相似度。

【输入输出样例】

　Input

4
8 ACBDCADB
6 CDDABC
50 -10 -20 -10
-10 50 -30 -20 
-20 -30 50 -20
-10 -20 -20 50
-30 -40 -20 -10

　Output

100

【样例解释】

　　一种相似度最大的方案如下：

　　相似度为：\((-30) + (50) + (-20) + 50 + (-20) + 50 + (-10) + 50 + (-20) = 100\)

【来源】

　　Mr.he