#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
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){
vector<pair<ll,ll>> g[m+2];
for(ll i=0; i<m; i++){
for(ll j=0; j<m; j++){
if(y[i]==x[j] && b[i]<=a[j]){
ll cw=c[j];
for(ll k=0; k<w; k++){
if(b[i]<l[k] && r[k]<a[j]) cw+=t[y[i]];
}
g[i+1].push_back({j+1,cw});
}
}
}
for(ll i=0; i<m; i++){
if(x[i]==0){
ll cw=c[i];
for(ll k=0; k<w; k++){
if(r[k]<a[i]) cw+=t[0];
}
g[0].push_back({i+1,cw});
}
if(y[i]==n-1){
ll cw=0;
for(ll k=0; k<w; k++){
if(b[i]<l[k]) cw+=t[n-1];
}
g[i+1].push_back({m+1,cw});
}
}
ll dist[m+2]={};
for(ll i=1; i<=m+1; i++){
dist[i]=INF;
}
bool vis[m+2]={};
priority_queue<pair<ll,ll>> q; q.push({0,0});
while(!q.empty()){
ll curr=q.top().second;
q.pop();
if(vis[curr]) continue;
vis[curr]=1;
for(auto nxt:g[curr]){
if(dist[nxt.first]>dist[curr]+nxt.second){
dist[nxt.first]=dist[curr]+nxt.second;
q.push({-dist[nxt.first],nxt.first});
}
}
}
if(dist[m+1]==INF) return -1;
else return dist[m+1];
}
