Это сложная версия задачи. Единственное отличие состоит в ограничениях на \(q\). Вы можете делать взломы, только если обе версии задачи сданы.
Смотритель зоопарка учил \(q\) своих овечек как писать и как складывать. \(i\)-я овечка должна написать ровно \(k\) неотрицательных чисел, сумма которых равна \(n_i\).
Как ни странно, у овечек есть свои суеверия насчет цифр, и они верят, что цифры \(3\), \(6\) и \(9\) счастливые. Для них удача числа зависит от его десятичного представления; удача всего числа является суммой удачи каждой из его цифр, а удача каждой цифры зависит от величины и позиции согласно следующей таблице. Например, удача числа \(319\) равна \(F_{2} + 3F_{0}\).
Каждая овечка хочет максимизировать сумму удач выписанных \(k\) чисел. Можете ли вы помочь овечкам?
Выходные данные
Выведите \(q\) строк, где \(i\)-я строка содержит максимальную сумму удач всех чисел, которые написала \(i\)-я овечка.
Примечание
В первом тесте \(57 = 9 + 9 + 39\). Три цифры \(9\) дают вклад \(1 \cdot 3\), а \(3\) в позиции десятков дает вклад \(2 \cdot 1\). Таким образом, сумма удач равна \(11\).
Во втором тесте \(63 = 35 + 19 + 9\). Сумма удач равна \(8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3 4 5 6
2
57
63
|
11
8
|