//khodaya komak kon
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxw=maxn*4;
vector<int>allind;
long long n,m,w,allt[maxn];
long long inf=1e17;
int dproot[maxw];
int kaf=(1<<19),root=0;
struct segment{
struct node{
int rc,lc,w;
node(){
rc=lc=w=0;
}
};
int ts=(1<<20);
node seg[(1<<20)*20];
segment(){
for(int i=1;i<kaf;i++){
seg[i].rc=((i<<1)^1);
seg[i].lc=(i<<1);
}
}
int upd(int i,int l,int r,int tl,int tr,int w){
if(l>r||l>tr||r<tl||tl>tr){
return i;
}
if(l>=tl&&r<=tr){
seg[ts]=seg[i];
seg[ts].w+=w;
ts++;
return ts-1;
}
int m=(l+r)>>1;
int fts=ts;
ts++;
seg[fts]=seg[i];
seg[fts].lc=upd(seg[fts].lc,l,m,tl,tr,w);
seg[fts].rc=upd(seg[fts].rc,m+1,r,tl,tr,w);
return fts;
}
int pors(int i,int l,int r,int tl,int tr){
int ret=0;
while(true){
ret+=seg[i].w;
if(l>=tl&&r<=tr){
return ret;
}
int m=(l+r)>>1;
if(tl<=m){
i=seg[i].lc;
r=m;
}else{
i=seg[i].rc;
l=m+1;
}
// return pors(seg[i].rc,m+1,r,tl,tr)+pors(seg[i].lc,l,m,tl,tr)+seg[i].w;
}
}
}seg;
struct func{
long long x0,w,ind;
func(){
x0=0;
ind=0;
w=inf;
}
long long get(long long inda){
inda=min(inda,(long long)allind.size()-1);
if(inda<x0){
return w;
}
//cout<<"wtf: "<<allind[x0]<<" "<<allind[inda]<<" "<<seg.pors(dproot[x0+1],0,kaf-1,inda,inda)<<endl;
return w+allt[ind]*seg.pors(dproot[x0+1],0,kaf-1,inda,inda);
}
bool operator ==(func f){
return (f.x0==x0&&f.w==w);
}
}fakefunc;
struct lichao{
struct node{
int l,r;
node(){
l=r=-1;
}
func f;
};
vector<node> segl;
void create(int sz){
sz+=2;
segl.resize(sz);
}
int te=1;
int gor(int i){
if(segl[i].r==-1){
segl[i].r=te;
te++;
}
return segl[i].r;
}
int gol(int i){
if(segl[i].l==-1){
segl[i].l=te;
te++;
}
return segl[i].l;
}
void add(func f,int i=0,int l=0,int r=1e6){
if(l==r){
return ;
}
if(segl[i].f==fakefunc){
segl[i].f=f;
return ;
}
int m=(l+r)/2;
if(segl[i].f.get(l)>f.get(l)){
swap(segl[i].f,f);
}
if(l==r-1){
return ;
}
if(segl[i].f.get(m)<=f.get(m)){
add(f,gor(i),m,r);
}else{
swap(segl[i].f,f);
add(f,gol(i),l,m);
}
}
long long pors(int w,int i=0,int l=0,int r=1e6){
if(l==r){
return 0;
}
long long ret=segl[i].f.get(w);
long long m=(l+r)>>1;
if(w>=m&&segl[i].r!=-1){
ret=min(ret,pors(w,segl[i].r,m,r));
}
if(w<m&&segl[i].l!=-1){
ret=min(ret,pors(w,segl[i].l,l,m));
}
return ret;
}
}lich[maxn];
struct yal{
int u,v,l,r,w;
}alle[maxn];
vector<int>adj[maxw];
int cnt[maxn];
vector<pair<int,int>>allw;
vector<int>allwi[maxw];
vector<func>addy[maxw];
void preq(){
for(auto x:allw){
allwi[x.first].push_back(x.second);
}
for(long long i=maxw-1;i>=0;i--){
for(auto x:allwi[i]){
root=seg.upd(root,0,kaf-1,x,(int)allind.size(),1);
}
dproot[i]=root;
}
}
long long 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;
w=W;
for(int i=0;i<n;i++){
allt[i]=T[i];
}
allind.push_back(0);
for(int i=0;i<m;i++){
allind.push_back(A[i]);
allind.push_back(B[i]);
}
for(int i=0;i<w;i++){
allind.push_back(L[i]);
allind.push_back(R[i]);
}
sort(allind.begin(),allind.end());
allind.resize(unique(allind.begin(),allind.end())-allind.begin());
for(int i=0;i<m;i++){
A[i]=lower_bound(allind.begin(),allind.end(),A[i])-allind.begin();
B[i]=lower_bound(allind.begin(),allind.end(),B[i])-allind.begin();
}
for(int i=0;i<w;i++){
L[i]=lower_bound(allind.begin(),allind.end(),L[i])-allind.begin();
R[i]=lower_bound(allind.begin(),allind.end(),R[i])-allind.begin();
allw.push_back(make_pair(L[i],R[i]));
}
preq();
for(int i=0;i<m;i++){
alle[i].u=X[i];
alle[i].v=Y[i];
alle[i].w=C[i];
alle[i].l=A[i];
alle[i].r=B[i];
cnt[alle[i].v]++;
// //cout<<"wtf "<<alle[i].l<<endl;
adj[alle[i].l].push_back(i);
// //cout<<"nago"<<endl;
}
for(int i=0;i<n;i++){
// //cout<<"injy"<<endl;
lich[i].create(cnt[i]);
// //cout<<"oonjy"<<endl;
func f;
if(i==0){
f.w=0;
}else{
f.w=inf;
}
// //cout<<"salam"<<endl;
f.x0=0;
f.ind=i;
lich[i].add(f);
// //cout<<"by"<<endl;
}
////cout<<"salam"<<endl;
for(int i=0;i<maxw;i++){
for(auto x:addy[i]){
lich[x.ind].add(x);
}
for(auto x:adj[i]){
long long w=lich[alle[x].u].pors(alle[x].l-1);
w+=alle[x].w;
//cout<<"pors: "<<alle[x].u<<" "<<alle[x].v<<" "<<allind[alle[x].l]<<" "<<allind[alle[x].r]<<" "<<alle[x].w<<" "<<w<<endl;
func f;
f.ind=alle[x].v;
f.w=w;
f.x0=alle[x].r;
addy[alle[x].r].push_back(f);
}
}
if(lich[n-1].pors(maxw+1)>=inf){
return -1;
}
return lich[n-1].pors(maxw+1);
}
