#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
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) {
struct Train {
int start_planet, end_planet, depart_time, arrive_time;
long long cost;
};
vector<Train> trains(M);
for (int i = 0; i < M; ++i) {
trains[i] = {X[i], Y[i], A[i], B[i], (long long)C[i]};
}
int max_time = 1001; // Large enough to cover all possible times
// Find actual max time from train schedules
for (const auto& train : trains) {
max_time = max(max_time, train.arrive_time);
}
for (int i = 0; i < W; ++i) {
max_time = max(max_time, R[i]);
}
max_time = min(max_time + 1, 1001);
// DP[planet][time][mask] = min cost to reach this state
map<tuple<int,int,int>, long long> dp;
dp[{0, 0, 0}] = 0;
priority_queue<tuple<long long, int, int, int>,
vector<tuple<long long, int, int, int>>,
greater<tuple<long long, int, int, int>>> pq;
pq.push({0, 0, 0, 0}); // cost, planet, time, mask
while (!pq.empty()) {
auto [cost, planet, time, mask] = pq.top();
pq.pop();
auto state = make_tuple(planet, time, mask);
if (dp.count(state) && dp[state] < cost) continue;
// Check if we reached destination with all meals
if (planet == N - 1 && mask == (1 << W) - 1) {
return cost;
}
// Option 1: Take meals on current planet at current time (pay cost)
for (int meal = 0; meal < W; ++meal) {
if (((mask >> meal) & 1) == 0 && L[meal] <= time && time <= R[meal]) {
int new_mask = mask | (1 << meal);
long long new_cost = cost + T[planet];
auto new_state = make_tuple(planet, time, new_mask);
if (!dp.count(new_state) || dp[new_state] > new_cost) {
dp[new_state] = new_cost;
pq.push({new_cost, planet, time, new_mask});
}
}
}
// Option 2: Take any train leaving from current planet at or after current time
for (const auto& train : trains) {
if (train.start_planet == planet && train.depart_time >= time) {
int new_mask = mask;
// Mark meals that are fully covered by train interval as free
for (int meal = 0; meal < W; ++meal) {
if (((new_mask >> meal) & 1) == 0) {
if (L[meal] >= train.depart_time && R[meal] <= train.arrive_time) {
new_mask |= (1 << meal);
}
}
}
long long new_cost = cost + train.cost;
auto new_state = make_tuple(train.end_planet, train.arrive_time, new_mask);
if (!dp.count(new_state) || dp[new_state] > new_cost) {
dp[new_state] = new_cost;
pq.push({new_cost, train.end_planet, train.arrive_time, new_mask});
}
}
}
}
return -1;
}
