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 testcase will contain two integers 1 ≤ N, M ≤ 2000, the length of each subsequence.
The next line will contain 26 integers (1 ≤ P_{i} ≤ 10^{5}), 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 testcase, 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
rushi2001:
20210612 09:34:32
Just a Straight forward LCS . 

Rafail Loizou:
20201117 01:44:35
Use your functions stack memory N*M array will fit. Or you can get TLE instead. 

shorifulsoumic:
20201116 14:33:50
You have to find subsequence. Not substring.


rum3r:
20200529 08:42:57
AC in one go! YEAH BOI ;) 

upen3103:
20200510 19:37:13
AC in 1 go! 

abhimanyu_1998:
20191229 19:28:36
cakewalk! 

r0ck1n70sh:
20190807 09:51:45
Does anyone know why getting SIGSEV error in test case 15.


khaja_mohammad:
20190718 17:57:14
Is it required to generate all common subsequences?? If yes, someone give me a hint. Thanks in advance. 

g_unit:
20190705 10:30:49
Last edit: 20190705 10:31:08 

avik26091998:
20181205 20:10:47
Just LCS. 
Added by:  Morass 
Date:  20171008 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Tunisian Collegiate Training Contest  Round #01 