题目描述

张琪曼喜欢和李旭琳玩这样一个游戏，首先她们在地上写出两个字符串， 张琪曼指出两个字符串中的同一个字符，然后她得到这个字符所代表的一个奖励 分数,这时李旭琳会擦除两个字符及它们前面的所有字符,直到最后张琪曼找不 出了为止。比如两个字符串分别为"$\red{abc}$"和"$\red{cab}$",假设擦除任意一个字符的奖 励分都为$\red{1,}$首先张琪曼会指出第一个串的第$\red{1}$个字符和第二个串的第$\red{2}$个字 符$\red{a,}$擦除后两个串变成"$\red{bc}$"和"$\red{b}$",然后她会指出$\red{b,}$最后游戏结束,她得两分。 现在张琪曼想知道她能得到最多的奖励分是多少?

输入格式

第一行一个数字$\red{n(n≤}$$\red{26),}$表示串一共可能出现的字母数。

接下来$\red{n}$行,每行一个字母和一个数字,表示擦除该字母得到的奖励分。

接下来两行,表示游戏开始的字符串,字符串只会包含给出的字母。(长度$\red{≤}$$\red{100}$)

输出格式

一个数表示最大奖励分。

样例

输入样例

3
a 1
b 10
c 100
abc
cab

输出样例

100