#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector <int>
const int NM = 1000;
const ll inf = 1e18;
namespace subtask1{
int N, M, W, f[NM+5][NM+5];
vi T, X, Y, A, B, C, L, R, od;
ll d[NM+5];
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 = NM; i >= 0; i--)
for (int j = i+1; j <= NM; 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;
}
}
ll solve(int N, int M, int W, vi T, vi X, vi Y, vi A, vi B, vi C, vi L, vi R){
return subtask1::solve(N, M, W, T, X, Y, A, B, C, L, R);
}
