#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 (v<<10) | mask
auto key = [&](int v, int m) { return ((long long)v << 10) | m; };
priority_queue<State> pq;
pq.push({0, 0, 0, 0});
dist[key(0, 0)] = 0;
while (!pq.empty()) {
auto [t, c, v, mask] = pq.top();
pq.pop();
if (dist[key(v, mask)] < c) continue;
if (v == N - 1 && mask == (1 << W) - 1) {
return c;
}
// Take meals on current planet for cost if meal time is exactly inside waiting period
for (int i = 0; i < W; i++) {
if (!(mask & (1 << i)) && L[i] <= t && t <= R[i]) {
int nmask = mask | (1 << i);
long long nc = c + T[v];
if (!dist.count(key(v, nmask)) || dist[key(v, nmask)] > nc) {
dist[key(v, nmask)] = nc;
pq.push({t, nc, v, nmask});
}
}
}
// Take train routes from current planet at or after current time
for (auto &e : g[v]) {
if (e.a >= t) {
int nmask = mask;
for (int i = 0; i < W; i++) {
// Meal must be fully inside train interval to be free
if (!(mask & (1 << i)) && L[i] >= e.a && R[i] <= e.b) {
nmask |= (1 << i);
}
}
long long nc = c + e.c;
if (!dist.count(key(e.y, nmask)) || dist[key(e.y, nmask)] > nc) {
dist[key(e.y, nmask)] = nc;
pq.push({e.b, nc, e.y, nmask});
}
}
}
}
return -1;
}
