#include <bits/stdc++.h>
using namespace std;
struct Train {
int x, y, a, b, c;
};
struct State {
int planet, time, meals_mask;
long long cost;
bool operator>(const State &other) const {
return cost > other.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<Train> trains(M);
for (int i = 0; i < M; i++) {
trains[i] = {X[i], Y[i], A[i], B[i], C[i]};
}
// Meals time intervals and total required meals
// Precompute all meals and their time windows
// DP Dijkstra state space:
// State: (planet, time, meals_mask)
// meals_mask - bitmask representing which meals have been taken
// time up to max 10 as problem constraints say times ≤ 10
//
// Since constraints are small (N,M,W ≤ 10), this approach is feasible.
int max_time = 10;
long long INF = 1e15;
// cost[planet][time][meals_mask] = minimal cost to be here
vector<vector<vector<long long>>> cost(N, vector<vector<long long>>(max_time+1, vector<long long>(1 << W, INF)));
priority_queue<State, vector<State>, greater<State>> pq;
// Start at planet 0, time 0, no meals taken
cost[0][0][0] = 0;
pq.push({0, 0, 0, 0});
auto meal_allowed_at = [&](int meal_idx, int t) {
return (t >= L[meal_idx] && t <= R[meal_idx]);
};
while (!pq.empty()) {
State cur = pq.top();
pq.pop();
if (cost[cur.planet][cur.time][cur.meals_mask] < cur.cost) continue;
// If reached planet N-1 with all meals taken
if (cur.planet == N-1 && cur.meals_mask == (1 << W) - 1) {
return cur.cost;
}
// Option 1: Take meals on the current planet if waiting (pay cost)
// or eat free on a train (on train means time interval on any train route?)
// Here, "waiting" means not on train, so if we do not move to next train yet,
// we pay cost per meal on planet
// Try taking any meal not yet taken, at current time if allowed
for (int i = 0; i < W; i++) {
if (!(cur.meals_mask & (1 << i)) && meal_allowed_at(i, cur.time)) {
int new_mask = cur.meals_mask | (1 << i);
// Can eat free on train route that covers this time - to check
// but here we only store state on planet, meals taken here cost T[cur.planet]
// So only pay if waiting on planet (no train now)
long long new_cost = cur.cost + T[cur.planet];
if (new_cost < cost[cur.planet][cur.time][new_mask]) {
cost[cur.planet][cur.time][new_mask] = new_cost;
pq.push({cur.planet, cur.time, new_mask, new_cost});
}
}
}
// Option 2: Take a train starting from current planet at or after current time
// Transfer time is zero, so we can only board trains where start planet == cur.planet and departure time >= cur.time
for (int i = 0; i < M; i++) {
if (trains[i].x == cur.planet && trains[i].a >= cur.time) {
// On train interval [A[i], B[i]] meals are free (if meal time in this range)
// So take meals for free on this train on the time interval
int new_mask = cur.meals_mask;
for (int m = 0; m < W; m++) {
if (!(new_mask & (1 << m))) {
// If meal window overlaps train interval, can take free
if (!(R[m] < trains[i].a || L[m] > trains[i].b)) {
new_mask |= (1 << m);
}
}
}
long long new_cost = cur.cost + trains[i].c;
if (new_cost < cost[trains[i].y][trains[i].b][new_mask]) {
cost[trains[i].y][trains[i].b][new_mask] = new_cost;
pq.push({trains[i].y, trains[i].b, new_mask, new_cost});
}
}
}
// Option 3: Wait time forward if no train (increase time by 1)
// Only if next time <= max_time
if (cur.time < max_time) {
// Waiting means pay per meal if eaten at this new time
// But we do not know here if any meals taken at new time, so no cost added here except meals when taken
if (cur.cost < cost[cur.planet][cur.time+1][cur.meals_mask]) {
cost[cur.planet][cur.time+1][cur.meals_mask] = cur.cost;
pq.push({cur.planet, cur.time+1, cur.meals_mask, cur.cost});
}
}
}
// No way to reach planet N-1 with all meals
return -1;
}
