#include "train.h"
#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define tdii tuple <double, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int N = 1e5 + 5;
const int inf = 1e18;
long long solve(int32_t n, int32_t m, int32_t k, vector<int32_t> p, vector<int32_t> x, vector<int32_t> y,
vector<int32_t> a, vector<int32_t> b, vector<int32_t> c, vector<int32_t> l, vector<int32_t> r) {
vector <tiii> food;
for (int i = 0; i < k; i++) {
food.emb(l[i], r[i], p[i]);
}
sort(all(food));
vector <int> pref(k + 1);
for (int i = 0; i < k; i++) pref[i + 1] = pref[i] + get <2> (food[i]);
l.emb(0), r.emb(0);
sort(all(l)), sort(all(r));
vector <tiiii> adj[n + 1];
for (int i = 0; i < m; i++) {
adj[x[i]].emb(a[i], b[i], c[i], y[i]);
}
for (int i = 0; i < n; i++) sort(all(adj[i]));
priority_queue <tiiii, vector <tiiii>, greater <tiiii>> q; q.emplace(0, 0, 0, 1);
map <pii, int> dis[n + 1]; dis[0][{0, 1}] = 0;
int ans = inf;
while (!q.empty()) {
auto [w, u, idx, fidx] = q.top(); q.pop();
pii curr = {idx, fidx};
if (dis[u].find(curr) != dis[u].end() && w > dis[u][curr]) continue;
if (idx + 1 < adj[u].size()) {
int nxtf = upper_bound(all(r), get <0> (adj[u][idx + 1])) - r.begin();
nxtf = max(nxtf, fidx);
int nw = w + (nxtf - fidx) * p[u];
if (dis[u].find({idx + 1, nxtf}) == dis[u].end() || nw < dis[u][{idx + 1, nxtf}]) {
dis[u][{idx + 1, nxtf}] = nw;
q.emplace(dis[u][{idx + 1, nxtf}], u, idx + 1, nxtf);
}
}
if (adj[u].size() > idx) {
auto [aa, bb, ww, v] = adj[u][idx];
int bnxtf = lower_bound(all(l), bb + 1) - l.begin(); bnxtf = max(bnxtf, fidx);
int anxtf = upper_bound(all(r), aa) - r.begin(); anxtf = max(anxtf, fidx);
int nw = w + ww + max(0ll, anxtf - fidx) * p[u];
if (v == n - 1) ans = min(ans, nw + max(0ll, (k - bnxtf + 1)) * p[v]);
int nxt = lower_bound(all(adj[v]), make_tuple(bb, 0, 0, 0)) - adj[v].begin();
if (nxt < adj[v].size()) {
if (dis[v].find({nxt, bnxtf}) == dis[v].end() || nw < dis[v][{nxt, bnxtf}]) {
dis[v][{nxt, bnxtf}] = nw;
q.emplace(dis[v][{nxt, bnxtf}], v, nxt, bnxtf);
}
}
}
}
return (ans == inf ? -1ll : ans);
}
