题目描述

在一个火车旅行非常受欢迎的国度，你提前规划了一年的火车旅行。接下来一年里，你要旅行的日子通过数组 days 给出，其中每一项是一个从 $1$ 到 $365$ 的整数，代表你计划旅行的日期。火车票有三种不同的销售方式：

• 一张为期一天的通行证售价为 costs[0] 美元。
• 一张为期七天的通行证售价为 costs[1] 美元。
• 一张为期三十天的通行证售价为 costs[2] 美元。

通行证允许在指定天数内无限制地旅行。你需要计算完成给定列表 days 中每一天的旅行所需要的最低消费。

输入格式

输入包含三行：

1. 第一行是一个整数 n，表示你计划旅行的天数。
2. 第二行是一个整数数组 days，表示你计划旅行的日期，按严格递增顺序排列，数组长度为 n。
3. 第三行是一个包含三个整数的数组 costs，分别表示一天、七天和三十天通行证的售价。

输出格式

输出一个整数，表示完成给定列表 days 中每一天的旅行所需要的最低消费。

样例

6
1 4 6 7 8 20
2 7 15

11

12
1 2 3 4 5 6 7 8 9 10 30 31
2 7 15

17

提示

样例解释

• 样例1：

  • 在第$1$天，购买一张为期一天的通行证，花费 $2$。
  • 在第$3$天，购买一张为期七天的通行证，覆盖第$3$至第$9$天，花费 $7$。
  • 在第$20$天，再次购买一张为期一天的通行证，花费 $2$。
  • 总共花费 $11$。

• 样例2：

  • 在第$1$天，购买一张为期三十天的通行证，覆盖第$1$至第$30$天，花费 $15$。
  • 在第$31$天，购买一张为期一天的通行证，花费 $2$。
  • 总共花费 $17$。

数据范围

• 1 <= n <= 365
• days 中的元素按严格递增顺序排列，且 1 <= days[i] <= 365
• costs.length == 3
• 1 <= costs[i] <= 1000