2072 - 公交乘车

题目描述

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

公里数 1 2 3 4 5 6 7 8 9 10
付费金额 12 21 31 40 49 58 69 79 90 101

一辆公交车单次行驶的公里数一定不超过 10 公里,一个乘客如果打算乘坐公交车完成 n 公里(1 \le n \le 100)的行程,他可以选择无限次的换车来完成行程。

请问,他最少要花多少钱?

输入

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

第二行一个整数 n 表示,旅客的总路程数。(1 \le n \le 100

输出

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

样例

输入

12 21 31 40 49 58 69 79 90 101
15

输出

147
来源

动态规划 背包

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 683
通过人数 527
金币数量 1 枚
难度 入门


上一题 下一题