Это сложная версия задачи. Единственное отличие состоит в ограничениях на $$$q$$$. Вы можете делать взломы, только если обе версии задачи сданы.
Смотритель зоопарка учил $$$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$$$-я овечка.
3 1 2 3 4 5 6 2 57 63
11 8
В первом тесте $$$57 = 9 + 9 + 39$$$. Три цифры $$$9$$$ дают вклад $$$1 \cdot 3$$$, а $$$3$$$ в позиции десятков дает вклад $$$2 \cdot 1$$$. Таким образом, сумма удач равна $$$11$$$.
Во втором тесте $$$63 = 35 + 19 + 9$$$. Сумма удач равна $$$8$$$.
