#include <bits/stdc++.h>
using namespace std;
#define int long long
#define a first
#define b second
#define pb push_back
#define endl '\n'
using vi = vector <int32_t>;
int solve(int32_t n, int32_t m, int32_t w, vi t, vi x, vi y, vi a, vi b, vi c, vi l, vi r) {
sort(l.begin(), l.end()); sort(r.begin(), r.end());
vector <int> cc(m);
for(int i = 0; i < m; i++) {
cc[i] = c[i];
}
for(int i = 0; i < m; i++) {
int v1 = lower_bound(r.begin(), r.end(), a[i])-r.begin();
cc[i] -= ((int)(w-v1))*((int)t[x[i]]);
int v2 = upper_bound(l.begin(), l.end(), b[i])-l.begin();
cc[i] += ((int)((w-v2)))*((int)t[y[i]]);
// cout << cc[i] << " " << v1 << " " << v2 << endl;
}
vector <vector <vector <int>>> adj(n+1);
for(int i = 0; i < m; i++) adj[x[i]].pb({y[i], a[i], b[i], cc[i]});
vector <int> dis(n+2, 1e18); dis[0] = 0;
priority_queue <vector <int>, vector <vector <int>>, greater <vector <int>>> que;
que.push({0, 0, 0});
while(!que.empty()) {
int node = (que.top())[0];
int time = (que.top())[1];
int d = (que.top()[2]);
que.pop();
if(dis[node] != d) continue;
for(auto i:adj[node]) {
if(i[1] < time) continue;
if((i[3]+d) < dis[i[0]]) {
dis[i[0]] = i[3]+d;
que.push({i[0], i[2], dis[i[0]]});
}
}
}
if(dis[n-1] == 1e18) return -1;
if(w == 0) return dis[n-1];
return (int)(dis[n-1]+((int)t[0]*w));
}
// signed main() {
// //your code goes here
// ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
// cout << solve (3, 3, 100000, {2000000, 30, 40}, {0, 1, 0}, {1, 2, 2},
// {1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19}) << endl;
// return 0;
// }
