Problem E
Royal Delivery

Mario is submitting a letter via the royal mail to proclaim his love to Princess Peach. However, the Royal Toad Delivery Service is incredibly greedy and they charge for each character used in his message. However, Mario has devised a secret compression strategy known only to himself and Princess Peach. When writing a series of the same character $C$ multiple times, Mario can instead write it as a number $R$ and the character $C$, to indicate that $C$ is repeated $R$ times. For numbers $R$ that have multiple digits, the cost is the sum of the digits of $R$. For example, some choices for compressing the string $BBB$ are $3B$, $B2B$, $2B1B$, or even leaving it as $BBB$. Note that Mario cannot compress any sequence of characters that have already undergone compression (ie $OOOO \rightarrow 3OO \rightarrow 32O$ is not allowed since “3O” has already been compressed).

However, it seems that the Royal Toads are clever and they have devised that people might try to create workarounds using this kind of system. Consequently, they decide to penalize numbers differently than characters, charging higher fees for larger digits. Given the cost for a letter and the cost for each digit, what is the minimum cost that Mario will be forced to pay, assuming he compresses his string optimally?

For example, in the second sample test case, Mario is sending the message “ILOOOOOOOOOVEYOU”. One optimal compression of this string would be “ILO8OVEYOU” which has a cost of $53$.

However, in the second test case, if Mario wanted to compress the string “AAAAAAAAAAAAA” into “10AAAA”, the total cost would be $\text {cost}(1)+\text {cost}(0)+4\cdot \text {cost}(A)$ which is $19$.

Input

The first line of the input contains two space separated integers $N$ ($1 \leq N \leq 100 \, 000$) and $P$ $(0 \leq P \leq 10^9)$, denoting the number of blocks of letters in the original message that Mario wants to send and the price of any alphabetic character.
Then follow $N$ lines containing a space separated string and integer $s_ i$ and $r_ i$ representing that in Mario’s message, the next $r_ i$ characters are $s_ i$. It is guaranteed that $s_ i$ will be an uppercase English letter $A-Z$ and $1 \leq r_ i < 10^9$. It is also guaranteed that $s_ i \neq s_{i+1}$ for all $1 \leq i < N$.
The last line of the input contains 10 space separated numbers $c_0 \; c_1 \; \ldots \; c_9$ $(0 \leq c_ i \leq 10^9)$, where $c_ i$ represents the cost of using the digit $i$. It is guaranteed that $c_0 \leq c_1 \leq \ldots c_9$ and $c_0 = 0$, since the Toads think that a 0 would convey less information anyways (they cannot count very high).

Output

Output one line containing a single number equal to the minimum cost of sending a compressed letter.

1 2
A 13
0 11 11 11 11 11 11 11 11 11

19

8 5
I 1
L 1
O 9
V 1
E 1
Y 1
O 1
U 1
0 1 2 3 4 5 6 7 8 999

53