#include <bits/stdc++.h>
using namespace std;
struct Edge {
int y, a, b;
long long c;
};
struct State {
long long t, cost;
int v, mask;
bool operator<(const State &o) const {
return cost > o.cost;
}
};
long long solve(int N, int M, int W, vector<int> T,
vector<int> X, vector<int> Y,
vector<int> A, vector<int> B, vector<int> C,
vector<int> L, vector<int> R) {
vector<vector<Edge>> g(N);
for (int i = 0; i < M; i++)
g[X[i]].push_back({Y[i], A[i], B[i], (long long)C[i]});
const long long INF = 4e18;
unordered_map<long long, long long> dist; // encode state as (v << 10) | mask
auto key = [&](int v, int mask) { return ((long long)v << 10) | mask; };
priority_queue<State> pq;
pq.push({0, 0, 0, 0});
dist[key(0, 0)] = 0;
while (!pq.empty()) {
auto [time, cost, v, mask] = pq.top(); pq.pop();
if (dist[key(v, mask)] < cost) continue;
if (v == N - 1 && mask == (1 << W) - 1) return cost;
// Take meals on planet with cost if in proper meal time window
for (int i = 0; i < W; i++) {
if (!(mask & (1 << i)) && L[i] <= time && time <= R[i]) {
int nmask = mask | (1 << i);
long long new_cost = cost + T[v];
if (!dist.count(key(v, nmask)) || dist[key(v, nmask)] > new_cost) {
dist[key(v, nmask)] = new_cost;
pq.push({time, new_cost, v, nmask});
}
}
}
// Try to take train starting from planet v at/after current time
for (auto &e : g[v]) {
if (e.a >= time) {
int nmask = mask;
// Meal must lie fully inside train interval to be free
for (int i = 0; i < W; i++) {
if (!(mask & (1 << i)) && L[i] >= e.a && R[i] <= e.b) {
nmask |= 1 << i;
}
}
long long new_cost = cost + e.c;
if (!dist.count(key(e.y, nmask)) || dist[key(e.y, nmask)] > new_cost) {
dist[key(e.y, nmask)] = new_cost;
pq.push({e.b, new_cost, e.y, nmask});
}
}
}
}
return -1;
}
