题目背景

English Statement. You must submit your code at the Chinese version of the statement.

您可以点击 这里 下载本场比赛的选手文件。

You can click here to download all tasks and examples of the contest.

密码 / Password：rAnHoUyaSuoBaoMimaNijuEdefAngsHa2)2$1)0(2@0!

本场比赛所有题目从标准输入读入数据，输出到标准输出。

题目描述

有一个正整数 $n$，保证其只由数字 $1\sim 9$ 构成。

你可以做任意多次如下操作：

• 选择 $n$ 的一个数位 $x$，花费 $v_x$ 的代价删除它，注意，此时 $n$ 的数位个数会减少 $1$，$n$ 的值也会发生相应的变化；
• 或者，花费 $n$ 的代价把剩余的所有数位删除。

求把整个数删除的最小代价。

输入格式

从标准输入读入数据。

本题有多组测试数据。

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含一个正整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行一个正整数 $n$，表示这个数的初始值。
• 第二行九个正整数 $v_1,v_2,\dots,v_9$，表示删除每个数位的代价。

输出格式

输出到标准输出。

对于每组测试数据：

• 输出一行一个正整数，表示最小代价。

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

提示

【样例 1 解释】

对于第一组测试数据，最优操作方案如下：

• 删除数位 $2$，代价为 $10$，此时 $n$ 变为 $13$；
• 删除数位 $3$，代价为 $10$，此时 $n$ 变为 $1$；
• 删除 $n$ 的剩余所有数位，代价为 $1$。

总代价为 $10+10+1=21$，可以证明，这是代价的最小值。

对于第二组测试数据，一种最优操作方案如下：

• 删除第一个数位 $1$，代价为 $2$，此时 $n$ 变为 $121$；
• 删除最后一个数位 $1$，代价为 $2$，此时 $n$ 变为 $12$；
• 删除数位 $2$，代价为 $1$，此时 $n$ 变为 $1$；
• 删除 $n$ 的剩余所有数位，代价为 $1$。

总代价为 $2+2+1+1=6$。

【样例 2】

见选手目录下的 bargain/bargain2.in 与 bargain/bargain2.ans。

这个样例满足测试点 $3\sim 6$ 的约束条件。

【样例 3】

见选手目录下的 bargain/bargain3.in 与 bargain/bargain3.ans。

这个样例满足测试点 $11$ 的约束条件。

【样例 4】

见选手目录下的 bargain/bargain4.in 与 bargain/bargain4.ans。

这个样例满足测试点 $17,18$ 的约束条件。

【样例 5】

见选手目录下的 bargain/bargain5.in 与 bargain/bargain5.ans。

这个样例满足测试点 $23\sim 25$ 的约束条件。

---

【数据范围】

对于全部的测试数据，保证：

• $1\le t\le 10$；
• $1\le n< 10^{10^5}$；
• 对于任意 $1\le i\le 9$，$1\le v_i\le 10^5$；
• $n$ 由数字 $1\sim 9$ 构成。

测试点	$n<$	$v_i\le$	特殊性质
$1$	$100$	$10^5$	无
$2$	$10^3$
$3\sim 6$	$10^{18}$
$7\sim 9$	$10^{40}$
$10$	$10^{10^5}$		$n$ 由至多一种数字构成
$11$			$n$ 由至多两种数字构成
$12,13$			$n$ 由至多三种数字构成
$14\sim 16$	$10^{10^3}$		$v_1=v_2=v_3=\dots =v_9$
$17,18$	$10^{10^5}$
$19,20$	$10^{100}$	$100$	无
$21,22$	$10^{10^3}$	$10^3$
$23\sim 25$	$10^{10^5}$	$10^5$