题目描述

A 城市有一条非常特别的街道，该街道在每个公里的节点上都有一个公交车站，乘客可以在任意的公交站点上车，在任意的公交站点下车。乘客根据每次乘坐公交的公里数进行付费，请注意：不一定公里数越高，费用越高，这也是这条街道特别的地方。

一辆公交车单次行驶的公里数一定不超过 $10$ 公里，一个乘客如果打算乘坐公交车完成 $n$ 公里（$1\le n\le 100$）的行程，他可以选择无限次的换车来完成行程。请问，他最少要花多少钱？

输入格式

第一行十个整数，分别表示公交行走 $1$ 到 $10$ 公里的费用（$\le 500$）。注意这些数并无实际的经济意义，即行驶 $10$ 公里费用可能比行驶 $1$ 公里少。

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

输出格式

仅一个整数，表示最少费用。

样例

12 21 31 40 49 58 69 79 90 101
15

147

提示

样例解释

总路程 $15$ 公里的最优拆分方式为 $5$ 公里 $+ 5$ 公里 $+ 5$ 公里，总费用为 $49+49+49=147$，这是所有可能拆分中费用最低的方案。

数据范围

$1\le n\le 100$，费用 $\le 500$。

来源

动态规划