问题描述

在 A 城市有一条特殊的街道，该街道上每隔一公里就设有一个公交车站，乘客能够在任意站点上车，并在任意站点下车。乘客的付费金额依据其乘坐公交车的公里数而定，以下为乘坐不同公里数时的具体付费情况（需注意，费用并非随公里数的增加而递增，这是该街道的独特之处）：

每辆公交车单次行驶的公里数不会超过 10 公里。若一位乘客计划乘坐公交车完成 n 公里（1 ≤ n ≤ 100）的行程，并且他可以选择无限次换乘来达成该行程。

请你计算出这位乘客完成此行程所需支付的最少费用。

输入格式

第一行：包含十个整数，依次表示公交行驶 1 到 10 公里的费用，这些费用均为不超过 500 的正整数。需注意，这些费用之间并无实际经济意义上的固定关系，即行驶 10 公里的费用有可能低于行驶 1 公里的费用。 第二行：一个整数 n，表示旅客的总路程数，满足 1 ≤ n ≤ 100。

输出格式

仅输出一个整数，该整数代表完成 n 公里行程的最少费用。

样例

输入

12 21 31 40 49 58 69 79 90 101
15

输出

147

数据范围

• 公交行驶 1 到 10 公里的费用：均为不超过 500 的正整数。
• 旅客的总路程数 n：1 ≤ n ≤ 100。