这是问题的困难版本。唯一的区别在于 $$$q$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
Zookeeper 一直在教他的 $$$q$$$ 羊如何书写以及如何添加。第 $$$i$$$ 只羊必须准确地写出 $$$k$$$ 个非负整数,其总和为 $$$n_i$$$。
奇怪的是,羊对数字有迷信,认为数字 $$$3$$$、$$$6$$$ 和 $$$9$$$ 是幸运的。对他们来说,一个数字的命运取决于该数字的十进制表示形式;一个数字的命运等于其各个数字的命运之和,而一个数字的命运取决于它的值和位置,可以用下表来描述。例如,数字 $$$319$$$ 的财富为 $$$F_{2} + 3F_{0}$$$。
每只羊都希望使其所有 $$$k$$$ 写入的整数中的财富总和最大化。你能帮助他们吗?
输入
第一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq 999999$$$):每只羊必须写的数字数量。
下一行包含六个整数 $$$F_0$$$、$$$F_1$$$、$$$F_2$$$、$$$F_3$$$、$$$F_4$$$、$$$F_5$$$ ($$$1 \leq F_i \leq 10^9$$$):分配给每个数字的财富。
下一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 100\,000$$$):羊的数量。
接下来的 $$$q$$$ 行包含一个整数 $$$n_i$$$ ($$$1 \leq n_i \leq 999999$$$):第 $$$i$$$ 只羊必须写入的数字总和。
输出
打印 $$$q$$$ 行,其中第 $$$i$$$ 行包含第 $$$i$$$ 只羊的所有数字的最大财富总和。
示例
输入 #1
3 1 2 3 4 5 6 2 57 63
输出 #1
11 8
注意
在第一个测试用例中,$$$57 = 9 + 9 + 39$$$。三个 $$$9$$$ 贡献 $$$1 \cdot 3$$$,十位的 $$$3$$$ 贡献 $$$2 \cdot 1$$$。因此财富总额为$$$11$$$。
在第二个测试用例中,$$$63 = 35 + 19 + 9$$$。财富总和为$$$8$$$。