← 返回题目列表

Codeforces · 1606/C

C. 纸币

中文机器翻译题面 查看原题

在 Berland,使用 $$$n$$$ 不同类型的纸币。 $$$i$$$ 类型的纸币面值为 $$$10^{a_i}$$$ burles(burles 是伯兰使用的货币);第一种纸币的面额正是$$$1$$$。

让我们将 $$$f(s)$$$ 表示为精确表示 $$$s$$$ burles 所需的最小纸币数量。例如,如果 Berland 使用的纸币面额为 $$$1$$$、$$$10$$$ 和 $$$100$$$,则 $$$f(59) = 14$$$:可以使用面值为 $$$1$$$ burle 的 $$$9$$$ 纸币和面值为 $$$10$$$ burle 的 $$$5$$$ 纸币准确地表示 $$$9 \cdot 1 + 5 \cdot 10 = 59$$$ burles,而且没有办法用更少的钞票来做到这一点。

对于给定的整数 $$$k$$$,求不能用 $$$k$$$ 或更少的钞票表示的 burles $$$s$$$ 的最小正数(即 $$$f(s) > k$$$)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10; 1 \le k \le 10^9$$$)。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 = a_1 < a_2 < \dots < a_n \le 9$$$)。

输出

对于每个测试用例,打印一个整数 - 不能用 $$$k$$$ 或更少的钞票表示的 burles $$$s$$$ 的最小正数。

示例

输入 #1

4
3 13
0 1 2
2 777
0 4
3 255
0 1 3
10 1000000000
0 1 2 3 4 5 6 7 8 9

输出 #1

59
778
148999
999999920999999999