Problem Description

A person named A, who is an employee at Indeed, is sharpening their skills in string processing. The problem A is currently working on is as follows:

You want to create a string by concatenating several palindromes. Using a palindrome of length $i$ incurs a cost of $C_i$. Determine the minimum total cost required to create the string $S$. Note that a palindrome is a string that reads the same forwards and backwards. Also, keep in mind that using the same palindrome more than once incurs the cost for each use.

However, A was unable to solve this problem. Please write a program to solve this problem on A's behalf.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $ $ C_1 $ $ C_2 $ ... $ C_N $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 5000)$, which represents the length of the string $S$.
• The second line contains the string $S$, which is a string of length $N$ consisting only of lowercase alphabets (a-z).
• The third line contains $N$ integers separated by spaces, representing the costs of using palindromes. The $i\ (1\ ≦\ i\ ≦\ N)$th integer $C_i\ (1\ ≦\ C_i\ ≦\ 10^5)$ represents the cost of using a palindrome of length $i$.

Output Format

Output the minimum total cost required to create the string $S$ by concatenating several palindromes. End the output with a newline.

Sample Input and Output

Sample Input #1

9
indeednow
1 1 1 1 1 1 1 1 1

Sample Output #1

4

Sample Input #2

9
indeednow
10 4 1 99 99 99 99 99 99

Sample Output #2

74

Sample Input #3

12
abcbaabcbcbc
20 13 15 29 38 43 76 58 23 128 99999 100000

Sample Output #3

78

Notes/Hints

Partial Points

This problem has partial points:

• If you solve the dataset where $N\ ≦\ 200$, you will be awarded 40 points.
• If you solve all test cases, you will be awarded an additional 60 points.

Sample Explanation 1

In this input example, concatenating i + ndeedn + o + w results in a cost of $4$.

Sample Explanation 2

In this input example, concatenating i + ndeedn + o + w results in a cost of $129$, but concatenating i + n + d + ee + d + n + o + w results in a cost of $74$.

见题面 Input 部分

见题面 Output 部分