#include "train.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll=long long;
const int N=200010, S=1<<18;
const ll INF=1e18;
int n, m, k;
vector<int> t, x, y, a, b, c, l, r;
vector<pair<int, int>> vec;
deque<pair<int, ll>> val[N];
set<pair<int, ll>> cand[N];
vector<array<int, 5>> vec2;
vector<int> com;
class PST {
public:
PST() {root.push_back(new Node());}
void update(int v) {root.push_back(update(root.back(), 1, S, v));}
ll query(int p, int k) {return query(root.back(), 1, S, 1, k)-(p?query(root[p-1], 1, S, 1, k):0);}
int query2(int p, int q, ll v) {
int ret=S;
for(int s=1, e=S; s<=e; ) {
int m=(s+e)/2;
if(query(p, m)-query(q, m)>=v) ret=m, e=m-1;
else s=m+1;
}
return ret;
//return query2((p<root.size())?root[p]:NULL, (q<root.size())?root[q]:NULL, 1, S, v);
}
private:
struct Node { int v; Node *l, *r; };
vector<Node*> root;
Node* update(Node *prev, int s, int e, int k) {
Node *node=new Node();
if(prev) node->v=prev->v, node->l=prev->l, node->r=prev->r;
node->v++;
if(s==e) return node;
int m=(s+e)/2;
if(k<=m) {
if(prev) node->l=update(prev->l, s, m, k);
else node->l=update(NULL, s, m, k);
}
else {
if(prev) node->r=update(prev->r, m+1, e, k);
else node->r=update(NULL, m+1, e, k);
}
return node;
}
int query(Node *node, int s, int e, int l, int r) {
if(s>r || l>e || !node) return 0;
if(l<=s && e<=r) return node->v;
int m=(s+e)/2;
return query(node->l, s, m, l, r)+query(node->r, m+1, e, l, r);
}
int query2(Node *node1, Node *node2, int s, int e, ll v) {
if(s==e) return s;
int m=(s+e)/2;
if(((node2&&node2->l)?node2->l->v:0)-((node1&&node1->l)?node1->l->v:0)>=v)
return query2(node1?node1->l:NULL, node2?node2->l:NULL, s, m, v);
return query2(node1?node1->r:NULL, node2?node2->r:NULL, m+1, e, v);
}
}P;
void update(int i, pair<int, ll> v) {
while(val[i].size()>=2) {
pair<int, ll> tmp=val[i].back();
int k1=P.query2(lower_bound(all(vec), make_pair(tmp.first+1, 0))-vec.begin()+1, lower_bound(all(vec), make_pair(v.first+1, 0))-vec.begin()+1, (v.second-tmp.second+t[i]-1)/t[i]);
val[i].pop_back();
pair<int, ll> tmp2=val[i].back();
int k2=P.query2(lower_bound(all(vec), make_pair(tmp2.first+1, 0))-vec.begin()+1, lower_bound(all(vec), make_pair(tmp.first+1, 0))-vec.begin()+1, (tmp.second-tmp2.second+t[i]-1)/t[i]);
if(k1>=k2) {
val[i].push_back(tmp); break;
}
}
val[i].push_back(v);
}
ll query(int i, int x) {
int x_=x;
x=lower_bound(all(com), x)-com.begin();
while(val[i].size()>=2) {
ll v1=val[i].front().second+(ll)t[i]*P.query(lower_bound(all(vec), make_pair(val[i].front().first+1, 0))-vec.begin()+1, x);
pair<int, ll> tmp=val[i].front(); val[i].pop_front();
ll v2=val[i].front().second+(ll)t[i]*P.query(lower_bound(all(vec), make_pair(val[i].front().first+1, 0))-vec.begin()+1, x);
if(v1<v2) {
val[i].push_front(tmp); break;
}
}
if(val[i].empty()) return INF;
return val[i].front().second+(ll)t[i]*P.query(lower_bound(all(vec), make_pair(val[i].front().first+1, 0))-vec.begin()+1, x);
}
ll 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) {
n=N, m=M, k=W;
t=T, x=X, y=Y, a=A, b=B, c=C, l=L, r=R;
if(!k) ++k, l.push_back(1e9+1), r.push_back(1e9+1);
for(int i=0; i<k; i++) com.push_back(l[i]), com.push_back(r[i]), vec.emplace_back(l[i], r[i]);
sort(com.begin(), com.end());
sort(vec.begin(), vec.end());
for(int i=0; i<vec.size(); i++) P.update(lower_bound(all(com), vec[i].second)-com.begin()+1);
val[0].push_back({0, 0});
for(int i=0; i<m; i++) vec2.push_back({a[i], b[i], c[i], x[i], y[i]});
sort(vec2.begin(), vec2.end());
for(int i=0; i<vec2.size(); i++) {
while(!cand[vec2[i][3]].empty() && (*cand[vec2[i][3]].begin()).first<=vec2[i][0]) {
update(vec2[i][3], *cand[vec2[i][3]].begin());
cand[vec2[i][3]].erase(cand[vec2[i][3]].begin());
}
cand[vec2[i][4]].insert({vec2[i][1], query(vec2[i][3], vec2[i][0])+vec2[i][2]});
}
for(auto t:cand[n-1]) update(n-1, t);
ll ans=query(n-1, com.back()+1);
if(l.back()==1e9+1) ans-=t[n-1];
if(ans>=INF/2) ans=-1;
return ans;
}
