DZY Loves Strings

1000ms

262144K

Description:

DZY loves collecting special strings which only contain lowercase letters. For each lowercase letter c DZY knows its value w_c. For each special string s = s₁s₂... s_|s| (|s| is the length of the string) he represents its value with a function f(s), where

$\text{[math]}$

Now DZY has a string s. He wants to insert k lowercase letters into this string in order to get the largest possible value of the resulting string. Can you help him calculate the largest possible value he could get?

Input:

The first line contains a single string s (1 ≤ |s| ≤ 10³).

The second line contains a single integer k (0 ≤ k ≤ 10³).

The third line contains twenty-six integers from w_a to w_z. Each such number is non-negative and doesn't exceed 1000.

Output:

Print a single integer — the largest possible value of the resulting string DZY could get.

Sample Input:

abc
3
1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output:

Note:

In the test sample DZY can obtain "abcbbc", value = 1·1 + 2·2 + 3·2 + 4·2 + 5·2 + 6·2 = 41.

Informação

Provedor Codeforces

Código CF447B