P5855 「SWTR-3」Password

小 $\mathrm{A}$ 在茂密的森林里找到了一个宝箱。 宝箱设有密码锁，但小 $\mathrm{A}$ 不知道密码。

宝箱的密码由 $n$ 位数字组成，如果将它们连在一起写，就可以看作是一个长度为 $n$ 的字符串。 小 $\mathrm{A}$ 想通过猜的方式试出密码。对于每一位数字，都会有一个集合 $s_i$，表示小 $\mathrm{A}$ 第 $i$ 位的尝试范围。 同时，小 $\mathrm{A}$ 已经试过了 $k$ 个密码组合 $d_1,d_2,\dots,d_k$，**这些密码不一定符合上文中的“尝试范围”**。 小 $\mathrm{A}$ 想知道他最多还需要尝试多少次才可以试出宝箱的密码，如果永远试不出输出 $\mathrm{-1}$。

无

无

--- ### 样例说明 - 在样例 $1$ 中，小 $\mathrm{A}$ 可能试的密码组合有：`014,015,044,045,094,095,114,115,144,145,194,195` 共 $12$ 个数，其中包含密码，但因为 `145` 已经试过，所以小 $\mathrm{A}$ 最多还需尝试 $11$ 次。 - 在样例 $2$ 中，小 $\mathrm{A}$ 可能试的密码组合有：`13,14,23,24`，共 $4$ 个数，其中没有密码，所以小 $\mathrm{A}$ 永远试不出密码。 --- ### 数据范围与约定 **本题使用捆绑测试。** Subtask 编号 | $n\leq$ | 特殊性质 | 分数 :-: | :-: | :-: | :-: $1$ | $18$ | 答案为 $-1$ | $7$ $2$ | $1$ | 无 | $13$ $3$ | $6$ | 无 | $24$ $4$ | $18$ | $k=0$ | $21$ $5$ | $18$ | 无 | $35$ 对于 $100\%$ 的数据，有 $1\leq n\leq 18$，$0\leq k \leq\min(10^n-1,10^4)$。 保证 $d_i$ 不为密码。 --- 对于所有测试点，时间限制 $1\mathrm{s}$，空间限制 $128\mathrm{MB}$。