Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
G1. Lucky Numbers (Easy Version)

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThis is the easy version of the problem. The only difference is that in this version $$$q=1$$$. 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

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$$$ ($$$q = 1$$$): 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. In this version, there is only one line.

Output

Print $$$q$$$ lines, where the $$$i$$$-th line contains the maximum sum of fortune of all numbers of the $$$i$$$-th sheep. In this version, you should print only one line.

Examples

Input

3 1 2 3 4 5 6 1 57

Output

11

Input

3 1 2 3 4 5 6 1 63

Output

8

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2021 20:12:06 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|