Description

There is an integer $n$ consisting only of digits $1\sim 9$.

You can do an arbitrary number of operations on $n$ (possibly zero):

• Choose a digit of $n$ and delete it. Suppose the digit is $x$, this operation will cost $v_x$. Note that after this operation, the length of $n$ decreases by $1$, and the value of $n$ also changes;
• Delete all the remaining digits of $n$. This operation will cost $n$.

Find the minimum cost to delete all digits of $n$.

Input Format

Each test contains multiple test cases.

The first line of the input contains a single integer $c$ — the id of the test. $c=0$ represents that this is a sample test.

The second line contains a single integer $t$ — the number of test cases.

For each test case:

• The first line contains a single integer $n$ — the initial value of the integer.
• The second line contains nine integers $v_1,v_2,\ldots,v_9$ — the cost of deleting each digit.

Output Format

For each test case:

• Print a single integer in the only line of the output — the minimum cost.

0
3
123
10 10 10 10 10 10 10 10 10 
1121
2 1 2 2 2 2 2 2 2
987654321
1 2 3 4 5 6 7 8 9

21
6
45

Hint

Sample 1 Explanation

In the first test case, the optimal operations are:

• Delete digit $2$ with a cost of $10$. After that, $n$ becomes $13$;
• Delete digit $3$ with a cost of $10$. After that, $n$ becomes $1$;
• Delete all the remaining digits of $n$ with a cost of $1$.

The total cost is $10+10+1=21$. It can be shown that this is the minimum cost.

In the second test case, the optimal operations are:

• Delete the first digit $1$ with a cost of $2$. After that, $n$ becomes $121$;
• Delete the last digit $1$ with a cost of $2$. After that, $n$ becomes $12$;
• Delete digit $2$ with a cost of $1$. After that, $n$ becomes $1$;
• Delete all the remaining digits of $n$ with a cost of $1$.

The total cost is $2+2+1+1=6$.

Sample 2

See bargain/bargain2.in and bargain/bargain2.ans in the attachments.

This sample satisfies the constraints of test $3\sim 6$.

Sample 3

See bargain/bargain3.in and bargain/bargain3.ans in the attachments.

This sample satisfies the constraints of test $11$.

Sample 4

See bargain/bargain4.in and bargain/bargain4.ans in the attachments.

This sample satisfies the constraints of test $17,18$.

Sample 5

See bargain/bargain5.in and bargain/bargain5.ans in the attachments.

This sample satisfies the constraints of test $23\sim 25$.

Constraints

For all the tests, it is guaranteed that:

• $1\le t\le 10$;
• $1\le n< 10^{10^5}$;
• For each $1\le i\le 9$，$1\le v_i\le 10^5$;
• $n$ consists only of digits $1\sim 9$.