D. No Game No Life
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

To determine the fate of Immanity, Sora and Shiro are playing yet another game, this time against the flügel Azriel!

They are given a string $$$s$$$ of length $$$N$$$ consisting only of lowercase and uppercase English ASCII letters. They are also given a list $$$a$$$ of $$$N$$$ integers, each in the range $$$1 \leq a_i \leq 100$$$.

Azriel carefully constructs $$$M$$$ (not necessarily distinct) strings, also consisting only of lowercase and uppercase English ASCII letters.

Sora and Shiro then choose a (possibly empty) subset of lowercase and uppercase letters. Let's denote this set $$$S$$$.

Azriel's score $$$k$$$ is calculated through the following process:

  • For all characters $$$c$$$ in $$$S$$$, replace all occurrences of $$$c$$$ in $$$s$$$ with a dot (.). Note that characters are being replaced, not removed. Denote the new string $$$t$$$.
  • For each character $$$t_i$$$ in $$$t$$$, if $$$t_i$$$ is not equal to a dot, add $$$a_i$$$ to $$$k$$$.
  • For each of Azriel's strings $$$r_i$$$, count how many times $$$r_i$$$ appears as a substring of $$$t$$$ and subtract $$$c_i$$$ from $$$k$$$ for each appearance. (Again, note that Azriel's strings are not necessarily distinct; so for instance if $$$r_i = r_j$$$, then Azriel's score decreases by $$$c_i+c_j$$$ for each appearance of $$$r_i$$$ in $$$t$$$.)

Since Shiro and Sora must beat Azriel for the sake of Immanity, they must choose a subset of characters $$$S$$$ that minimizes Azriel's score. Help them by finding the minimum possible value of Azriel's final score, and also print a string $$$t$$$ which produces this score.

Input

The first line of input consists of two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq M \leq 30$$$).

The next line contains the string $$$s$$$, which consists of $$$N$$$ characters from the set $$$\{\texttt{a}-\texttt{z},\texttt{A}-\texttt{Z}\}$$$.

The next line contains $$$N$$$ space-separated integers $$$a_i$$$ ($$$1 \leq a_i \leq 100$$$).

The last $$$M$$$ lines each contain a string $$$r_i$$$ and an integer $$$c_i$$$ ($$$1 \leq c_i \leq 100$$$), separated by a space. Each $$$r_i$$$ consists of characters from the set $$$\{\texttt{a}-\texttt{z},\texttt{A}-\texttt{Z}\}$$$, and has length $$$1 \leq |r_i| \leq \min(N, 10^4)$$$.

Output

Print two lines of output. On the first line, print an integer: Azriel's minimum possible score over all choices of characters $$$S$$$ to replace.

On the second line, print the string $$$t$$$ that achieves this minimum possible score. If there are multiple possible such strings, print any one of them.

Example
Input
5 4
abcdb
1 1 2 2 3
b 2
b 3
bc 1
ab 3
Output
-8
ab..b
Note

In the sample input, the optimal choice of $$$S$$$ is $$$S=\{\texttt{c},\texttt{d}\}$$$. With this choice, Azriel gets a score of $$$1+1+3$$$ from the non-dot letters that remain in $$$t$$$. Since $$$\texttt{b}$$$ appears twice and $$$\texttt{ab}$$$ appears once in $$$t$$$, his final score is thus $$$1+1+3-2\cdot2-2\cdot3-1\cdot3 = -8$$$.