公路的起点到终点相距 $N$ 千米。途中可以任意换乘车辆，每辆车一次可以行驶 $1$～$10$ 千米，行驶恰好 $i$ 千米的费用为 $a_i$。各种里程的车辆数量不限。

请计算从起点到终点的最少乘车费用。注意，票价不一定随里程递增，例如行驶 $10$ 千米的费用可能比行驶 $1$ 千米更低。

输入格式

第一行包含 $10$ 个非负整数 $a_1,a_2,\ldots,a_{10}$，分别表示一次行驶 $1$～$10$ 千米的费用。

第二行包含一个正整数 $N$，表示公路总长度。

输出格式

输出一个整数，表示恰好到达终点所需的最少费用。

12 21 31 40 49 58 69 79 90 101
15

147

数据范围

$1\le N\le 10^6$，$0\le a_i\le 500$。

164 347 74 161 106 239 61 175 215 229
1

164

281 204 438 319 450 451 380 262 52 410
2

204