J. 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!

They are given a string $$$s$$$ of length $$$N$$$ consisting only of lowercase and uppercase English letters. The $$$i$$$th character in has an integer $$$a_i$$$ in the range $$$[1, 100]$$$.

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

Shiro then chooses a (possibly empty) subset of letters from the English alphabet. Let's denote this set as $$$S$$$.

Sora'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 as $$$t$$$.
  • For each character $$$t_i$$$ in $$$t$$$, if $$$t_i$$$ is not equal to a dot, add $$$a_i$$$ to $$$k$$$.
  • Each time one of Sora's strings $$$r_i$$$ appears as a susbstring of $$$t$$$, subtract $$$c_i$$$ from $$$k$$$.

Since Shiro wants to beat Sora, she will choose a subset of characters that minimizes Sora's score. You must help her by finding the minimum possible value of Sora's final score, and to also print a string $$$t$$$ which produces this score.

Input

The first line of input consists of two integers $$$N$$$ and $$$M$$$. ($$$1 \leq M,M \leq 20$$$)

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

The next line contains $$$N$$$ space-separated integers, corresponding to $$$a_1, a_2, ... a_N$$$. ($$$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$$$). Each $$$r_i$$$ consists of characters from the set $$$\{a-z,A-Z\}$$$, and $$$1 \leq |r_i| \leq N$$$. Note that not all $$$r_i$$$ are guaranteed to be unique.

Output

The first line of output contains an integer which is the minimum possible score of a string.

The second line contains a string $$$t$$$ with minimum possible score. If there are multiple correct answers, output any of them.

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

In the sample case, Sora gets a total of $$$1+1+3$$$ from the non dot letters in $$$t$$$. $$$b$$$ appears twice and $$$ab$$$ appears once, so his total score is $$$1+1+3-2-2-3 = -2$$$.