Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

Shocking Calculation

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 2.0 seconds

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.

  • Sample Input 1

    12
    5 10 6 8 1 2 6 9 3 4
    6 1000 2
    

    Sample Output 1

    12
    
  • Sample Input 2

    12
    1 10 4 7 1 7 3 7 2 9
    8 10 3
    

    Sample Output 2

    14
    
  • Sample Input 3

    12
    10 10 1 2 10 3 10 10 10 10
    0 0 0
    

    Sample Output 3

    5