Shocking Calculation

You are door to door feijoa salesman making the rounds. You've arrived at the home of an Australian and unfortunately they do not understand your kiwi accent. You need to inform them of the price of feijoas but have no pen or paper around, but you do carry a calculator. You are determined to type the price in on the calculator to try and sell your feijoas.

It had been raining heavily and you find your calculator moist. All the number buttons are working, but the '$+$', '$*$', and '$=$' buttons are faulty. The '$+$', '$*$', and '$=$' buttons will each only work once then they are completely disabled. Your calculator also has a strange quirk, the display only shows an answer upon pressing '$=$'. In other words, until you press the '$=$' button, nothing will display on the calculator (no intermediate calculations are displayed).

Pressing buttons on the calculator shocks you. You do not like getting shocked because it hurts. Each button hurts according to its hurt value.

Find the way to show your Australian friend the price of feijoas that minimizes the total hurt value for all shocks you receive by pressing your calculator's buttons.

Input

• A line with the price ($N$) you are trying to display ($1 \le N \le 100\,000$).
• The hurt values due to a shock from the corresponding number button $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$.
• Followed by a line with hurt values of the '$+$', '$*$', '$=$' buttons respectively.

It is guaranteed for each button to be an integer hurt value, where $0 \le hurt\ value \le 1000$.

Output

The minimal amount of cumulative hurt you will receive to display the price.

Subtasks

• Subtask 1 (+40%): All hurt values are $1$.
• Subtask 2 (+40%): $N \le 10\,000$, with a hurt value of $1000$ for the '$*$' button, and a hurt value of at most $10$ for all other buttons.
• Subtask 3 (+20%): No additional limitations.

Sample explanation

In the first sample, the best way to make 12 is by pressing '$4$', '$+$', '$8$', and '$=$'. This results in a hurt value of $1+6+3+2 = 12$.

Note:

Your calculator follows the order of BEDMAS (it will multiply before addition).

The answer assumes you cannot hold the calculator upside down.

Python programmers should submit solutions with Python 3.6 (PyPy 7.3) selected instead of Python 3.8, as it may make the submission run faster. We cannot guarantee that all solutions submitted for Python 3.8 will pass with the given time limit.