ADASEQEN - Ada and Subsequence


Ada the Ladybug has two string which she wants to give to her friends. As she doesn't want to distinguish between them, she wants to use only some common subsequence. Firstly she wanted to simply use the longest common subsequence but then she realized it wouldn't be kosher.

She assigned a positive value to each letter. Now she wants to find the most expensive subsequence.

Input

The first line of each test-case will contain two integers 1 ≤ N, M ≤ 2000, the length of each subsequence.

The next line will contain 26 integers (1 ≤ Pi ≤ 105), the price of each letter.

The next line will contain string of length N consisting of lowercase english alphabet.

The next line will contain string of length M consisting of lowercase english alphabet.

Output

For each test-case, print the cost of the most expensive common subsequence.

Example Input

4 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
abcd
dbca

Example Output

2

Example Input

3 3
1 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
baa
aab

Example Output

7

Example Input

4 5
1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6
zbbz
bbzbb

Example Output

14

Example Input

3 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
abc
def

Example Output

0

hide comments
abhimanyu_1998: 2019-12-29 19:28:36

cakewalk!

r0ck1n70sh: 2019-08-07 09:51:45

Does anyone know why getting SIGSEV error in test case 15.

khaja_mohammad: 2019-07-18 17:57:14

Is it required to generate all common subsequences?? If yes, someone give me a hint. Thanks in advance.

g_unit: 2019-07-05 10:30:49

Last edit: 2019-07-05 10:31:08
avik26091998: 2018-12-05 20:10:47

Just LCS.

priyanshul: 2018-11-21 09:16:45

my code is working fine in codeblocks but is showing WA in Online Judge, pls help.
http://discuss.spoj.com/t/https-www-spoj-com-problems-adaseqen/31209

vjvjain0: 2018-10-07 22:33:06

4 7
1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6
zbbz
bbczcbb

going to be 14

dewa251202: 2018-10-02 16:28:25

no fast i/o : 0.05 sec
fast i/o : 0.13 sec

lmao

sdeven_0245: 2018-07-30 08:56:01

simple one

nikhil2504: 2018-02-27 19:14:02

same as LCS


Added by:Morass
Date:2017-10-08
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Tunisian Collegiate Training Contest - Round #01