Migrated from Lutece 723 公交换乘

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

假设某条街上每一公里就有一个公共汽车站，并且乘车费用如下表：

而任意一辆汽车从不行驶超过$10$公里。某人想恰好行驶$n$公里，假设他可以任意次换车，请你帮他找到一种乘车方案，使得总费用最小。

注意：$10$公里的费用比$1$公里小的情况是允许的。

Input

每组输入共两行，第一行为$10$个不超过$200$的整数，依次表示行驶$1\sim 10$公里的费用，相邻两数间用一个空格隔开；第二行为某人想要行驶的公里数。

Output

输出仅一行，包含一个整数，表示行使这么远所需要的最小费用。

Samples

12 21 31 40 49 58 69 79 90 101
15

147

Resources

2013 UESTC ACM Training for Dynamic Programming