题目背景

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

密码：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$