## 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 substring 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 ≤ 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 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

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 |