#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector <int>
#define isz(a) (int)(a).size()
const int NM = 2e5;
const ll inf = 1e18;
namespace subtask1{
int N, M, W, f[2005][2005];
vi T, X, Y, A, B, C, L, R, od;
ll d[2005];
int calc(int x, int y){
if (x > y) return 0;
return f[x][y];
}
ll solve(int _N, int _M, int _W, vi _T, vi _X, vi _Y, vi _A, vi _B, vi _C, vi _L, vi _R){
N = _N, M = _M, W = _W;
T = _T, X = _X, Y = _Y, A = _A, B = _B, C = _C, L = _L, R = _R;
od.clear();
for (int i = 0; i < M; i++) od.push_back(i);
sort(od.begin(), od.end(), [&](int i, int j){
return B[i] < B[j];
});
memset(f, 0, sizeof(f));
for (int i = 0; i < W; i++) f[L[i]][R[i]]++;
for (int i = 2000; i >= 0; i--)
for (int j = i+1; j <= 2000; j++)
f[i][j] += f[i+1][j]+f[i][j-1]-f[i+1][j-1];
for (int t1 = 0; t1 < M; t1++){
int i = od[t1];
if (X[i] == 0) d[i] = 1LL*calc(0, A[i]-1)*T[X[i]]+C[i];
else d[i] = +inf;
for (int t2 = 0; t2 < t1; t2++){
int j = od[t2];
if (Y[j] != X[i]) continue;
if (B[j] > A[i]) continue;
d[i] = min(d[i], d[j]+1LL*calc(B[j]+1, A[i]-1)*T[X[i]]+C[i]);
}
}
ll ans = +inf;
for (int t = 0; t < M; t++){
if (Y[t] != N-1) continue;
ans = min(ans, d[t]+1LL*calc(B[t]+1, NM)*T[N-1]);
}
if (ans == +inf) return -1;
return ans;
}
}
namespace subtask2{
struct segtree{
vector <ll> data;
void reset(int n){
data.assign(4*n+5, +inf);
}
void update(int id, int l, int r, int i, ll val){
if (i < l || i > r) return;
if (l == r){
data[id] = min(data[id], val);
return;
}
int mid = (l+r)/2;
update(2*id, l, mid, i, val);
update(2*id+1, mid+1, r, i, val);
data[id] = min(data[2*id], data[2*id+1]);
}
ll get(int id, int l, int r, int u, int v){
if (u > v || v < l || u > r) return +inf;
if (l >= u && r <= v) return data[id];
int mid = (l+r)/2;
return min(get(2*id, l, mid, u, v), get(2*id+1, mid+1, r, u, v));
}
} ST[NM+5];
int N, M, W;
vi T, X, Y, A, B, C, L, R, od;
ll d[NM+5];
vector <int> arr[NM+5];
int sz[NM+5];
ll solve(int _N, int _M, int _W, vi _T, vi _X, vi _Y, vi _A, vi _B, vi _C, vi _L, vi _R){
N = _N, M = _M, W = _W;
T = _T, X = _X, Y = _Y, A = _A, B = _B, C = _C, L = _L, R = _R;
for (int i = 0; i < N; i++) arr[i].clear();
for (int i = 0; i < M; i++){
arr[X[i]].push_back(A[i]);
arr[Y[i]].push_back(B[i]);
}
for (int i = 0; i < N; i++){
sort(arr[i].begin(), arr[i].end());
arr[i].erase(unique(arr[i].begin(), arr[i].end()), arr[i].end());
sz[i] = isz(arr[i]);
ST[i].reset(sz[i]);
}
od.clear();
for (int i = 0; i < M; i++) od.push_back(i);
sort(od.begin(), od.end(), [&](int i, int j){
return B[i] < B[j];
});
for (int t = 0; t < M; t++){
int i = od[t];
if (X[i] == 0) d[i] = C[i];
else{
int p = lower_bound(arr[X[i]].begin(), arr[X[i]].end(), A[i])-arr[X[i]].begin()+1;
d[i] = ST[X[i]].get(1, 1, sz[X[i]], 1, p)+C[i];
}
int q = lower_bound(arr[Y[i]].begin(), arr[Y[i]].end(), B[i])-arr[Y[i]].begin()+1;
ST[Y[i]].update(1, 1, sz[Y[i]], q, d[i]);
}
ll ans = +inf;
for (int t = 0; t < M; t++){
if (Y[t] != N-1) continue;
ans = min(ans, d[t]);
}
if (ans == +inf) return -1;
return ans;
}
}
ll solve(int N, int M, int W, vi T, vi X, vi Y, vi A, vi B, vi C, vi L, vi R){
if (W == 0) return subtask2::solve(N, M, W, T, X, Y, A, B, C, L, R);
return subtask1::solve(N, M, W, T, X, Y, A, B, C, L, R);
}
