J. Roman Numerals
time limit per test
1 s
memory limit per test
256 megabytes
input
standard input
output
standard output

There are seven characters in Roman numerals: I, V, X, L, C, D, M, representing $$$1$$$, $$$5$$$, $$$10$$$, $$$50$$$, $$$100$$$, $$$500$$$, $$$1000$$$ respectively.

Now you will use Roman numerals and Arabic numerals to represent a positive integer in decimal. For example, $$$\texttt{X}2 = 10\times 10^1 + 2 \times 10^0=102$$$, $$$\texttt{IV}=1\times 10^1+5\times 10^0=15$$$.

For each digit, there is a certain cost for its representation. Find the minimum cost to represent a positive integer using a mixed representation.

Input

The first line contains a positive integer $$$T$$$ ($$$1\le T\le 2\cdot 10^3$$$), indicating the number of test cases.

For each test case, the first line contains a positive integer $$$n$$$ ($$$1\le n\le 10^{18}$$$), indicating the integer to be represented.

The second line contains 10 positive integers $$$c_0,c_1,\ldots,c_9$$$ ($$$1\le c_i\le 10^7$$$), representing the cost of using the Arabic numerals $$$0$$$ to $$$9$$$ in the mixed representation.

The third line contains 7 positive integers $$$c_{\texttt{I}},c_{\texttt{V}},\ldots,c_{\texttt{M}}$$$ ($$$1\le c_i\le 10^7$$$), representing the cost of using the Roman numerals I to M in the mixed representation.

Output

For each test case, output a single integer, representing the minimum cost required to represent the integer in decimal using a mixed representation of Roman numerals and Arabic numerals.

Example
Input
5
102
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
112
1 5 5 1 1 1 1 1 1 1
1 1 1 1 1 1 1
150
1 1 1 1 1 1 1 1 1 1
5 5 5 5 5 5 5
114514
10 5 5 1 1 1 1 1 1 1
1 1 1 1 1 1 1
1919810
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
Output
2
7
3
6
6
Note

$$$102$$$ can be represented as $$$\texttt{X}2$$$, $$$\texttt{I}02$$$, and $$$102$$$. The representation with the minimum cost is $$$\texttt{X}2$$$, requiring a cost of $$$2$$$.

$$$112$$$ can be represented as $$$\texttt{I}12$$$, $$$1\texttt{I}2$$$, $$$\texttt{II}2$$$ and $$$112$$$. The representation with the minimum cost is $$$\texttt{II}2$$$, requiring a cost of $$$7$$$.

$$$150$$$ can be represented as $$$\texttt{XL}$$$, $$$\texttt{5C}$$$, $$$10\texttt{L}$$$, etc. The representation with the minimum cost is $$$150$$$, requiring a cost of $$$3$$$.