#include "train.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (ll)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
using namespace std;
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) {
const ll INF = 1e18;
map<pair<ll, ll>, vector<tuple<ll, ll, ll>>> g;
vector<ll> adj[N];
for(ll i = 0;i<M;++i){
g[{X[i], A[i]}].pb({C[i], Y[i], B[i]});
adj[X[i]].pb(A[i]);
adj[Y[i]].pb(B[i]);
}
for(ll i = 0;i<N;++i){
sort(all(adj[i]));
for(ll j = 1;j<ls(adj[i]);++j){
g[{i, adj[i][j - 1]}].pb({0, i, adj[i][j]});
}
}
if(adj[0].empty()) return -1;
g[{0, 0}].pb({0, 0, adj[0].front()});
L.pb(-1);
R.pb(-1);
sort(all(L));
sort(all(R));
priority_queue<tuple<ll, ll, ll, ll>, vector<tuple<ll, ll, ll, ll>>, greater<tuple<ll, ll, ll, ll>>> pq;
map<tuple<ll, ll, ll>, ll> dp;
pq.push({0, 0, 0, 0});
dp[{0, 0, 0}] = 0;
while(!pq.empty()){
auto [k, x, a, s] = pq.top(); pq.pop();
if(dp[{x, a, s}] != k) continue;
ll lax = upper_bound(all(L), a) - L.begin();
ll r = R[lax - 1];
for(auto [c, y, b]:g[{x, a}]){
ll cost = c + k;
ll rax = --lower_bound(all(R), b) - R.begin();
if(x == y) cost += max(0LL, rax - lax + 1) * T[x];
if(x == y and !s and r >= a and r <= b) cost += T[x];
if((x != y or (s and r >= b)) and (!dp.count({y, b, 1}) or dp[{y, b, 1}] > cost)){
dp[{y, b, 1}] = cost;
pq.push({cost, y, b, 1});
}
else{
if(!dp.count({y, b, 0}) or dp[{y, b, 0}] > cost){
dp[{y, b, 0}] = cost;
pq.push({cost, y, b, 0});
}
}
}
}
ll b = adj[N - 1].back();
ll ans = INF;
ll lax = upper_bound(all(L), b) - L.begin();
ll cost = (W + 1 - lax) * T[N - 1];
ll l = L[lax - 1];
ll r = R[lax - 1];
if(dp.count({N - 1, b, 0})) ans = min(ans, dp[{N - 1, b, 0}] + cost + (r >= b ? T[N - 1] : 0));
if(dp.count({N - 1, b, 1})) ans = min(ans, dp[{N - 1, b, 1}] + cost);
if(ans == INF) ans = -1;
return ans;
}
