#include "train.h"
#include <algorithm>
// #include <iostream>
// #include <map>
#include <numeric>
// #include <queue>
// #include <set>
#include <vector>
const long long inf = 1e15;
const int N = 1e3 + 1;
std::vector<std::pair<std::pair<int, int>, int>> adj[N][N];
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) {
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::vector<long long>>>(
max_time + 1));
for (int i = 0; i < N; ++i) {
std::vector<long long> init_meals(W);
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[j] = t_val;
tot += t_val;
}
if (i != N - 1) {
tot += (long long)W * inf;
}
dp[i][max_time] = {tot, init_meals};
}
std::vector meals(max_time + 1, std::vector<bool>(W));
std::vector<bool> meals_rn(W);
for (int t = max_time; t >= 0; --t) {
for (auto &i : meals_add[t]) {
meals_rn[i] = true;
}
for (int i = t; i <= max_time; ++i) {
for (int j = 0; j < W; ++j) {
if (!meals_rn[j]) {
continue;
}
meals[i][j] = true;
}
}
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;
}
long long t_val = T[i];
t_val = std::min(t_val, meals_had[j]);
cost -= meals_had[j];
meals_had[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 (int i = 0; i < W; ++i) {
if (meals[u.second][i]) {
cost -= meals_had[i];
meals_had[i] = 0;
}
}
for (int j = 0; j < W; ++j) {
if (L[j] > t or t > R[j]) {
continue;
}
long long t_val = T[i];
t_val = std::min(t_val, meals_had[j]);
cost -= meals_had[j];
meals_had[j] = t_val;
cost += t_val;
}
if (cost < dp[i][t].first) {
dp[i][t] = {cost, meals_had};
}
}
}
for (auto &i : meals_remove[t]) {
meals_rn[i] = false;
}
}
// dp[0][0] = time 0, city 0
long long ans = dp[0][0].first;
if (ans >= inf) {
ans = -1;
}
return ans;
}
