Lucky Numbers (Hard Version)
Contest: Codeforces Raif Round 1 (Div. 1 + Div. 2)
Difficulty rating: 3000
Tags: dp, greedy

This is the hard version of the problem. The only difference is in the constraint on $$$q$$$. You can make hacks only if all versions of the problem are solved.

Zookeeper has been teaching his $$$q$$$ sheep how to write and how to add. The $$$i$$$-th sheep has to write exactly $$$k$$$ non-negative integers with the sum $$$n_i$$$.

Strangely, sheep have superstitions about digits and believe that the digits $$$3$$$, $$$6$$$, and $$$9$$$ are lucky. To them, the fortune of a number depends on the decimal representation of the number; the fortune of a number is equal to the sum of fortunes of its digits, and the fortune of a digit depends on its value and position and can be described by the following table. For example, the number $$$319$$$ has fortune $$$F_{2} + 3F_{0}$$$.

Each sheep wants to maximize the sum of fortune among all its $$$k$$$ written integers. Can you help them?

Input format:
The first line contains a single integer $$$k$$$ ($$$1 \leq k \leq 999999$$$): the number of numbers each sheep has to write.

The next line contains six integers $$$F_0$$$, $$$F_1$$$, $$$F_2$$$, $$$F_3$$$, $$$F_4$$$, $$$F_5$$$ ($$$1 \leq F_i \leq 10^9$$$): the fortune assigned to each digit.

The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 100\,000$$$): the number of sheep.

Each of the next $$$q$$$ lines contains a single integer $$$n_i$$$ ($$$1 \leq n_i \leq 999999$$$): the sum of numbers that $$$i$$$-th sheep has to write.

Output format:
Print $$$q$$$ lines, where the $$$i$$$-th line contains the maximum sum of fortune of all numbers of the $$$i$$$-th sheep.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$57 = 9 + 9 + 39$$$. The three $$$9$$$'s contribute $$$1 \cdot 3$$$ and $$$3$$$ at the tens position contributes $$$2 \cdot 1$$$. Hence the sum of fortune is $$$11$$$.

In the second test case, $$$63 = 35 + 19 + 9$$$. The sum of fortune is $$$8$$$.

Example input:
3
1 2 3 4 5 6
2
57
63

Example output:
11
8

Editorial:
Suppose in our final solution, there is a certain position (ones, tens...) that has two digits which are not $$$0$$$, $$$3$$$, $$$6$$$, or $$$9$$$. Let these two digits are $$$a$$$ and $$$b$$$. If $$$a+b \leq 9$$$, we can replace these two digits with $$$0$$$, and $$$a+b$$$. Otherwise, we can replace these two digits with $$$9$$$ and $$$a+b-9$$$. By doing this, our solution is still valid as the sum remains the same, and the total fortune will not decrease since $$$a$$$ and $$$b$$$ are not $$$3$$$, $$$6$$$ or $$$9$$$.
As such, in the optimal solution, there should be at most one number that consists of digits that are not $$$0$$$, $$$3$$$, $$$6$$$ or $$$9$$$. Let's call this number that has other digits $$$x$$$.
Easy Version
Since there's only one query, we can try all possibilities of $$$x$$$. The question reduces to finding the maximum sum of fortune among K-1 numbers containing the digits $$$0$$$, $$$3$$$, $$$6$$$ and $$$9$$$ that sum up to exactly $$$n-r$$$. We can model this as a 0-1 knapsack problem, where the knapsack capacity is $$$n-r$$$.
For the ones position, the value (fortune) can be increased by $$$F_0$$$ for a weight of $$$3$$$ a total of $$$3(k-1)$$$ times, so we can create $$$3(k - 1)$$$ objects of weight $$$3$$$ and value $$$F_0$$$. For tens it's $$$F_1$$$ for a weight of $$$30$$$, and so on. Since there are many duplicate objects, we can group these duplicate objects in powers of $$$2$$$. For example, $$$25$$$ objects can be grouped into groups of $$$1$$$, $$$2$$$, $$$4$$$, $$$8$$$, $$$10$$$.
This runs in $$$O(ndlogk)$$$ where $$$d$$$ is the number of digits (6 in this case)
Hard Version
In the hard version, we are not able to search all $$$n$$$ possibilities for the last number $$$x$$$ as there are many queries.
Using the 0-1 knapsack with duplicates, we have computed the dp table for the first $$$k-1$$$ numbers. The rest is incorporating the last number into the dp table. We can do this by considering each digit separately. Then, we can update the dp table by considering all possible transitions for all digits from $$$0$$$ to $$$9$$$.