题目内容

小塔有一个长度为$n$，由前$k$个小写字母组成的字符串(保证$n$为偶数)。

小美想在小塔睡觉的时候把这个字符串用小塔的零花钱消除干净。小美每次可以选择该串的两个相邻的字符删除，删除后将串拼上，并花掉小塔一定数量的零花钱。

若某一次删除的相邻两个字符从左到右分别是a和b，则将花掉小塔$cost$($a,b$)块钱。小美希望他花掉的零花钱尽可能多，帮帮小美。

输入描述

第一行有两个整数$n,k$($1<=n<=500,1<=k<=26$)，分别代表小塔的字符串长度与字符串中的字符种类数(保证$n$为偶数且串的内容仅由前$k$个小写英文字母组成)。

接下来k行给出了一个$k*k$的由整数构成的矩阵。矩阵中第$i$行第$j$列的元素代表消除相邻的第$i$个字母和第$j$个字母所能花掉的钱数。

最后一行有一个长度为$n$的字符串，代表小塔的字符串。

输出描述

输出一个值，代表小美最多能花掉小塔多少零花钱。

样例1

输入

4 3
0 1 3
2 0 0
0 0 0
abac

输出

5

说明

如样例中先消除$ab$再消除$ac$则可花掉$1+3=4$元钱，先消除$ba$再消除$ac$则可花掉$2+3=5$元钱