You plan your train travel schedule one year in advance. The days of the year when you will travel are given as an integer array days, where each day is an integer from 1 to 365.

The train system sells tickets in three different ways:

a 1-day pass costs costs[0] dollars,

a 7-day pass costs costs[1] dollars,

a 30-day pass costs costs[2] dollars.

Each pass allows unlimited train travel for that many consecutive days.

For example, if you buy a 7-day pass on day 3, the pass covers travel on days 3, 4, 5, 6, 7, 8, and 9.

Return the minimum amount of money you need to cover all train travel days listed in days.

Example 1:

Input: days = [1,5,6,7,8,9,20,91], costs = [2,7,15]
Output: 13
Explanation:
Buy a 1-day pass on day 1. Cost: $2. Travel days covered: 1.
Buy a 7-day pass starting on day 5. Cost: $7. Travel days covered: 5, 6, 7, 8, 9.
Buy a 1-day pass on day 20. Cost: $2. Travel days covered: 20.
Buy a 1-day pass on day 91. Cost: $2. Travel days covered: 91.
Total cost: 2 + 7 + 2 + 2 = 13.

Example 2:

Input: days = [1, 3, 4, 20, 21, 22, 23, 24], costs = [2, 7, 15]
Output: 13
Explanation:
Buy a 1-day pass on day 1. Cost: $2. Travel days covered: 1.
Buy a 1-day pass on day 3. Cost: $2. Travel days covered: 3.
Buy a 1-day pass on day 4. Cost: $2. Travel days covered: 4.
Buy a 7-day pass starting on day 20. Cost: $7. Travel days covered: 20, 21, 22, 23, 24.
Total cost: 2 + 2 + 2 + 7 = 13.

Example 3:

Input: days = [320], costs = [2, 7, 15]
Output: 2
Explanation: There is only one travel day: day 320. The cheapest option is to buy one 1-day pass for $2.

Constraints

1 <= days.length <= 365

1 <= days[i] <= 365

days is sorted in strictly increasing order.

costs.length == 3

1 <= costs[i] <= 1000

84. Minimum Cost for Tickets