// #pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstdio>
#include <random>
#include <iomanip>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

#define PB emplace_back
#define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) { rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1]; }

const int N = 1e5, inf = 1e18;
int a, b, c, l[N + 5], r[N + 5], top, t[N + 5], dis[N + 5], d[N + 5];
struct node {
	int x, y, a, b, c;
} p[N + 5];
struct pii {
	int x, y, z;
} q[N + N + 5], s[N + 5];
struct stack {
	vector<pii> s;
	int l;
	int size() {return siz(s) - l;}
	pii &top() {return s.back();}
	pii &front() {return s[l];}
	void pop() {s.pop_back();}
	void push(pii x) {s.PB(x);}
	void pf() {++l;}
} sk[N + 5];

int rt[N + 5], ls[N * 20 + 5], rs[N * 20 + 5], w[N * 20 + 5], tot;
void add(int &n, int l, int r, int k, int p) {
	++tot;
	ls[tot] = ls[n], rs[tot] = rs[n], w[tot] = w[n] + p;
	n = tot;
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(k <= mid) add(ls[n], l, mid, k, p);
	else add(rs[n], mid + 1, r, k, p);
}
int ask(int n, int l, int r, int L) {
	if(r <= L || !n) return w[n];
	int mid = (l + r) >> 1;
	if(L <= mid) return ask(ls[n], l, mid, L);
	return w[ls[n]] + ask(rs[n], mid + 1, r, L);
}
int get(int u, int n, int k) {
	return dis[u] + ask(rt[p[u].b + 1], 1, top, k - 1) * d[n];
}

int mian() {
	sort(s + 1, s + c + 1, [&] (pii x, pii y) {
		return x.x > y.x;
	});
	int j = 1;
	per(i, top, 1) {
		rt[i] = rt[i + 1];
		for(; j <= c && s[j].x == i; ++j) add(rt[i], 1, top, s[j].y, 1);
	}
	sort(q + 1, q + b * 2 + 1, [&] (pii x, pii y) {
		return x.y < y.y || (x.y == y.y && x.z < y.z);
	});
	int ans = inf;
	memset(dis, 0x3f, sizeof(dis));
	rep(i, 1, 2 * b) {
		auto [x, y, z] = q[i];
		int u = p[x].x, v = p[x].y, w = p[x].c;
		if(!z) {
			if(v == a) {
				ans = min(ans, get(x, v, top));
				continue;
			}
			while(siz(sk[v]) && sk[v].top().y >= y && get(sk[v].top().x, v, sk[v].top().y) >= get(x, v, sk[v].top().y))
				sk[v].pop();
			if(siz(sk[v])) {
				auto [p, l, r] = sk[v].top();
				l = max(l, y);
				int res = r + 1;
				while(l <= r) {
					int mid = (l + r) >> 1;
					if(get(p, v, mid) >= get(x, v, mid)) res = mid, r = mid - 1;
					else l = mid + 1;
				}
				sk[v].top().z = res - 1;
				if(res <= top) sk[v].push(pii {x, res, top});
			}
			else sk[v].push(pii {x, y, top});
		}
		else {
			if(u == 1) {
				dis[x] = ask(rt[1], 1, top, y - 1) * d[1] + w;
				continue;
			}
			if(!siz(sk[u])) continue;
			while(sk[u].front().z < y) sk[u].pf();
			dis[x] = get(sk[u].front().x, u, y);
		}
	}
	return ans == inf ? -1 : ans;
}

#undef int
long long solve(int N, int M, int W, std::vector<int> T,
 std::vector<int> X, std::vector<int> Y,
 std::vector<int> A, std::vector<int> B, std::vector<int> C,
 std::vector<int> L, std::vector<int> R) {
	a = N, b = M, c = W;
	for(int x : A) t[++top] = x;
	for(int x : B) t[++top] = x;
	for(int x : L) t[++top] = x;
	for(int x : R) t[++top] = x;
	sort(t + 1, t + top + 1);
	top = unique(t + 1, t + top + 1) - t - 1;
	for(int &x : A) x = lower_bound(t + 1, t + top + 1, x) - t;
	for(int &x : B) x = lower_bound(t + 1, t + top + 1, x) - t;
	for(int &x : L) x = lower_bound(t + 1, t + top + 1, x) - t;
	for(int &x : R) x = lower_bound(t + 1, t + top + 1, x) - t;
	rep(i, 0, a - 1) d[i + 1] = T[i];
	rep(i, 0, c - 1) s[i + 1] = pii {L[i], R[i]};
	rep(i, 0, b - 1) {
		p[i + 1] = node {X[i] + 1, Y[i] + 1, A[i], B[i], C[i]};
		q[i * 2 + 1] = pii {i + 1, B[i], 0};
		q[i * 2 + 2] = pii {i + 1, A[i], 1};
	}
	return mian();
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cout << solve(3, 3, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},
 {1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19});
	return 0;
// 	cout << solve(3, 5, 6, {30, 38, 33}, {0, 1, 0, 0, 1}, {2, 0, 1, 2, 2},
 // {12, 48, 26, 6, 49}, {16, 50, 28, 7, 54}, {38, 6, 23, 94, 50},
 // {32, 14, 42, 37, 2, 4}, {36, 14, 45, 40, 5, 5});
	return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}