Bus Fare

Background

Special for beginners, ^_^

Problem Description

On a certain street there is a bus stop every kilometer, and the fare for riding is shown in the table below:

A single bus never travels more than $10$ kilometers. A person wants to travel $n$ kilometers ($0 < n \le 100$). Assuming he can change buses any number of times, help him find a riding plan that minimizes the cost (the case where the fare for $10$ km is smaller than the fare for $1$ km is allowed).

Note: all buses travel in the same direction.

Input Format

The input consists of two lines. The first line contains $10$ integers not exceeding $101$, denoting the fares for traveling $1 \sim 10$ kilometers respectively, separated by spaces.

The second line is the number of kilometers the person wants to travel.

Output Format

Output a single line containing one integer: the minimum cost for this test case.

Sample Input 1

12 21 31 40 49 58 69 79 90 101
15

Sample Output 1

147

Constraints

1s, 1024KiB for each test case.