Lucky Numbers (Hard Version)

题意翻译

给定 $q$ 个位数小于等于 $5$ 的数 $n_1, n_2 ... n_q$。 对于每一个数 $n$，他想把这个数划分成 $k$ 个数。一个数的权值是各个数位的权值和。一个数位的权值如下:  例如数字 $319$ 的权值就是 $F_2 + 3F_0$。 他想让划分出来的这些数权值和最大。 数据范围：$q \le 10^5, n \le 999999$，$F_i \le 10^9$

题目描述

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?

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

3
1 2 3 4 5 6
2
57
63

输出样例 #1

11
8

说明

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 $ .