#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());
for(int i = 0; i < m; i++) {
int v1 = lower_bound(r.begin(), r.end(), a[i])-r.begin();
c[i] -= (w-v1)*t[x[i]];
int v2 = upper_bound(l.begin(), l.end(), b[i])-l.begin();
c[i] += (w-v2)*(t[y[i]]);
}
vector <vector <vector <int>>> adj(n+1);
for(int i = 0; i < m; i++) adj[x[i]].pb({y[i], a[i], b[i], c[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;
return dis[n-1]+(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, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},
{1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19}) << endl;
return 0;
}
