<p>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 <code>days</code>. Each day is an integer from <code>1</code> to <code>365</code>.</p>

<p>Train tickets are sold in <strong>three different ways</strong>:</p>

<ul>
	<li>a <strong>1-day</strong> pass is sold for <code>costs[0]</code> dollars,</li>
	<li>a <strong>7-day</strong> pass is sold for <code>costs[1]</code> dollars, and</li>
	<li>a <strong>30-day</strong> pass is sold for <code>costs[2]</code> dollars.</li>
</ul>

<p>The passes allow that many days of consecutive travel.</p>

<ul>
	<li>For example, if we get a <strong>7-day</strong> pass on day <code>2</code>, then we can travel for <code>7</code> days: <code>2</code>, <code>3</code>, <code>4</code>, <code>5</code>, <code>6</code>, <code>7</code>, and <code>8</code>.</li>
</ul>

<p>Return <em>the minimum number of dollars you need to travel every day in the given list of days</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> days = [1,4,6,7,8,20], costs = [2,7,15]
<strong>Output:</strong> 11
<strong>Explanation:</strong> For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
<strong>Output:</strong> 17
<strong>Explanation:</strong> For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total, you spent $17 and covered all the days of your travel.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= days.length &lt;= 365</code></li>
	<li><code>1 &lt;= days[i] &lt;= 365</code></li>
	<li><code>days</code> is in strictly increasing order.</li>
	<li><code>costs.length == 3</code></li>
	<li><code>1 &lt;= costs[i] &lt;= 1000</code></li>
</ul>

#include <bits/stdc++.h>
using namespace std;

#ifdef ONLINE_JUDGE
#define STATER
#else
#define STATER freopen("E.txt", "w", stderr);
#endif

#define Cargs(x) template<class...x>
#define Carg(x) template<class x>
#define xl cout<<'\n';
Cargs(T) void out(T &&... s) {
	(void)initializer_list<int> {(cout << s << '\n', 0)...};
}
Cargs(T) void outc(T &&...s) {
	(void)initializer_list<int> {(cout << s << " ", 0)...};
}
Cargs(T) void oute(T &&...s) {
	(void)initializer_list<int> {(cout << s << ' ', 0)...};
	xl;
}
Cargs(T) void in(T &...s) {
	(void)initializer_list<int> {(cin >> s, 0)...};
}
Carg(T) void outv(const T &x, int s = 0, int e = numeric_limits<int>::max()) {
	auto it = x.begin();
	advance(it, s);
	for (int i = s; i < e && it != x.end(); ++i, ++it)
		outc(*it);
	xl;
}
#define TCS ios::sync_with_stdio(0);cin.tie(0); \
INT(t); for(int i=1; i<=t; i++){Case(i);solve();bl }
#define MOD (int)1e9 + 7
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define ppf pop_front
#define ff first
#define ss second
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define vii vector<vi>
#define vcc vector<vc>
#define vbb vector<vb>
#define vss vector<vs>
#define mii map<int, int>
#define mci map<char, int>
#define mic map<int, char>
#define mcvi map<char, vi>
#define mivi map<int, vi>
#define pii pair<int, int>
#define pci pair<char, int>
#define vpii vector<pii>
#define vpci vector<pci>
#define si set<int>
#define sc set<char>
#define pq priority_queue<int>
#define pqs priority_queue<int, vi, greater<int>>
#define prefix(x) partial_sum(all(x), begin(x))
#define suffix(x) partial_sum(rall(x), rbegin(x))
#define maxe(x) *max_element(all(x))
#define mine(x) *min_element(all(x))
#define maxeIndex(x) max_element(all(x)) - begin(x)-1
#define mineIndex(x) min_element(all(x)) - begin(x)-1
#define ub(x, y) upper_bound(all(x), y) - begin(x)
#define lb(x, y) lower_bound(all(x), y) - begin(x)
#define vfind(v, x) find(all(v), x)
#define vcount(s, x) count(all(s), x)
#define vsum(v) accumulate(all(v), 0LL)
#define csum(x) (x * (x + 1) >> 1)
#define mid(l, r) (int)(l + ((r - l) >> 1))
#define verase(v, x) v.erase(vfind(v, x))
#define vunique(v) v.erase(unique(all(v), end(v)))
#define vremove(v, x) v.erase(remove(all(v), x), end(v))
#define vrev(v) reverse(all(v));
#define lsb(x) (int)log2(x & -x)
#define msb(x) (x == 0 ? -1 : 31 - __builtin_clz(x))
#define setbit(x) __builtin_popcountll(x)
#define bin(x) bitset<32>(x)
#define andbit(i, j) (i & (1 << j))
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define VEC(T,v,n) vector<T> v(n); for (auto &x : v) cin >> x
#define VVEC(T,v,n,m) vector<vector<T>>v(n, vector<T>(m)); \
		for (auto &i : v)for (auto &j : i)cin >> j
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define OUT(x,y) out(x ? (y ? "YES" : "Yes") : (y ? "NO" : "No"))
Carg(x) class _F {
	x y;
  public:
	Carg(T)explicit _F(T &&z): y(std::forward<T>(z)) {}
	Cargs(a)decltype(auto) operator()(a &&...b) {
		return y(*this, std::forward<a>(b)...);
	}
};
Carg(x)decltype(auto) F(x &&z) {
	return _F<decay_t<x>>(std::forward<x>(z));
}
int solve(vi &d, vi &cd) {
	int n = sz(d);
	vi dp(n + 3, INT_MAX);
	auto rec = F([&](auto & self, int i)->int{
		if (i >= n)
			return 0;
		if (dp[i] != INT_MAX)
			return dp[i];
		int a = cd[0] + self(i + 1);
		int i2 = lb(d, 7 + d[i]);
		int b = cd[1] + self(i2);
		int i3 = lb(d, 30 + d[i]);
		int c = cd[2] + self(i3);
		return dp[i] = min({a, b, c});
	});
	rec(0);
	return dp[0];
}
class Solution {
public:
    int mincostTickets(vector<int>& d, vector<int>& c) {
        return solve(d,c);
    }
};
12400