Minimum Cost For Tickets

Problem Statement

You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days (sorted in ascending order). Each day is between 1 and 365.

Train tickets are sold in three different ways:

1-day pass costs costs[0] dollars
7-day pass costs costs[1] dollars
30-day pass costs costs[2] dollars

The passes allow that many days of consecutive travel.

Return the minimum number of dollars you need to travel every day in the given list of days.

Input Format

Line 1: Space-separated integers representing travel days. Line 2: Three space-separated integers representing costs of 1-day, 7-day, and 30-day passes.

Output Format

A single integer representing the minimum cost.

Examples

Example 1:

Input:
days = [1, 4, 6, 7, 8, 20]
costs = [2, 7, 15]

Output: 11

Buy a 1-day pass on day 1 (cost=2), a 7-day pass on day 4 covering days 4-10 (cost=7), and a 1-day pass on day 20 (cost=2). Total = 11.