题目描述

奇怪的街道上，在每公里处有一个汽车站，顾客可以根据他们乘坐汽车的公里数来付费。

下表就是一个里程与费用的价目表的样例:

没有一辆车子行驶超过 10 公里，如果一个顾客打算去 $n$ 公里远的地方，可以通过无限次的换车来完成旅程。最后要求费用最少。

输入格式

第一行十个整数，分别表示行走 $1-10$ 公里的费用 $a_{i}$ 。（有可能行驶 10 公里费用比行驶一公里还少)；

第二行一个整数 $n$ ，表示旅客的打算走的总路程数。

输出格式

一个整数，表示走 $n$ 公里，旅客最少的花费。

样例输入

12 21 31 40 49 58 69 79 90 101
15

样例输出

147

样例分析

如上所述。

数据范围

$100 \%$ 的数据: $1 \leq n \leq 100 ; 1 \leq a_{i} \leq 500$ 。