#include "train.h"
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
const long long inf = 1e15;
long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X,
std::vector<int> Y, std::vector<int> A, std::vector<int> B,
std::vector<int> C, std::vector<int> L, std::vector<int> R) {
std::map<std::pair<int, int>,
std::vector<std::pair<std::pair<int, int>, int>>>
adj;
int max_time = 0;
int max_l_i = 0, max_r_i = 0;
long long t_max = *std::max_element(T.begin(), T.end());
for (int i = 0; i < M; ++i) {
adj[{X[i], A[i]}].push_back({{Y[i], B[i]}, C[i]});
max_time = std::max(max_time, std::max({L[i], R[i], B[i]}));
}
std::vector<std::vector<int>> meals_add(max_time + 1),
meals_remove(max_time + 1);
for (int i = 0; i < W; ++i) {
meals_add[R[i]].push_back(i);
meals_remove[L[i]].push_back(i);
}
std::vector dp(
N, std::vector<std::pair<long long, std::set<std::pair<int, long long>>>>(
max_time + 1));
for (int i = 0; i < N; ++i) {
std::set<std::pair<int, long long>> init_meals;
long long tot = 0;
for (int j = 0; j < W; ++j) {
long long t_val = inf;
if (L[j] <= t_max and t_max <= R[j]) {
t_val = T[i];
}
init_meals.insert({j, t_val});
tot += t_val;
}
if (i != N - 1) {
tot += (long long)W * inf;
}
dp[i][max_time] = {tot, init_meals};
}
std::vector<std::set<int>> meals(max_time + 1);
std::set<int> meals_rn;
for (int t = max_time; t >= 0; --t) {
for (auto &i : meals_add[t]) {
meals_rn.insert(i);
}
for (int i = t; i <= max_time; ++i) {
for (auto &j : meals_rn) {
meals[i].insert(j);
}
}
for (int i = 0; i < N; ++i) {
if (t == max_time) {
continue;
}
dp[i][t] = dp[i][t + 1];
{ // update meals with station i
auto &meals_had = dp[i][t].second;
auto &cost = dp[i][t].first;
for (int j = 0; j < W; ++j) {
if (L[j] > t or t > R[j]) {
continue;
}
auto it = meals_had.lower_bound({j, -1});
long long t_val = T[i];
if (it != meals_had.end() and it->first == j) {
t_val = std::min(t_val, it->second);
meals_had.erase(it);
cost -= it->second;
}
meals_had.insert({j, t_val});
cost += t_val;
}
}
for (auto &[u, wt] : adj[{i, t}]) {
auto &meals_had = dp[u.first][u.second].second;
long long cost = wt + dp[u.first][u.second].first;
// take meals maybe
// time interval: [t, u.second]
for (auto &i : meals[u.second]) {
auto it = meals_had.lower_bound({i, -1});
if (it != meals_had.end() and it->first == i) {
meals_had.erase(it);
cost -= it->second;
}
meals_had.insert({i, 0});
}
for (int j = 0; j < W; ++j) {
if (L[j] > t or t > R[j]) {
continue;
}
auto it = meals_had.lower_bound({j, -1});
long long t_val = T[i];
if (it != meals_had.end() and it->first == j) {
t_val = std::min(t_val, it->second);
meals_had.erase(it);
cost -= it->second;
}
meals_had.insert({j, t_val});
cost += t_val;
}
dp[i][t] = std::min(dp[i][t], {cost, meals_had});
}
}
for (auto &i : meals_remove[t]) {
meals_rn.erase(i);
}
}
// dp[0][0] = time 0, city 0
long long ans = dp[0][0].first;
if (ans >= inf) {
ans = -1;
}
return ans;
}
