小明有一个长度为 ，由前 个小写英文字母组成的字符串（保证 为偶数）。 小亮想在小明睡觉的时候把这个字符串用小明的零花钱消除干净。 小亮每次可以选择该串的两个相邻的字符删除，删除后将串拼上，并花掉小明一定数量的零花钱。 若某一次删除的相邻两个字符从左到右分别是 和 ，则将花掉小明 块钱。小亮希望他花掉的零花钱尽可能多，帮帮小亮。

输入描述:

第一行有两个整数 ，分别代表小明的字符串长度与字符串中的字符种类数（保证 为偶数且串的内容仅由前 个小写英文字母组成）。接下来 行给出了一个 的由整数构成的矩阵。矩阵中第 行第 列的元素代表消除相邻的第 个字母和第 个字母所能花掉的钱数。最后一行有一个长度为 的字符串，代表小明的字符串。

输出描述:

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