#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(g))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

namespace whq {

constexpr int N = 1e5 + 9;
constexpr LL INF = 1e18;
int n, m, q;

LL C[N];

int d[N * 4], K;

struct edg {
  int u, v, w, s, t;
} e[N];

int lp[N], rp[N];

vi lis[N * 4];

int sum[N << 5], ls[N << 5], rs[N << 5], rt[N * 4], tot;

void ins (int x, int l, int r, int &p) {
  ++tot;
  sum[tot] = sum[p] + 1;
  ls[tot] = ls[p];
  rs[tot] = rs[p];
  p = tot;
  if (l == r) {
    return;
  }
  int md = (l + r) >> 1;
  x <= md ? ins(x, l, md, ls[p]) : ins(x, md + 1, r, rs[p]);
}

int qry (int ql, int qr, int l, int r, int p) {
  if (!p) {
    return 0;
  }
  if (ql <= l && r <= qr) {
    return sum[p];
  }
  int s = 0;
  int md = (l + r) >> 1;
  if (ql <= md) {
    s += qry(ql, qr, l, md, ls[p]);
  }
  if (md < qr) {
    s += qry(ql, qr, md + 1, r, rs[p]);
  }
  return s;
}

LL W (int l, int r, LL x) {
  if (l > r) {
    return INF;
  }
  l += 1;
  r -= 1;
  return l > r ? 0 : qry(l, K, 1, K, rt[r]) * x;
}

LL f[N];
int id[N];
vi atom[N], g[N];

struct tup {
  int p, l, r;
};
vector<tup> stk[N];

LL calc (int i, int j) {
  assert(e[i].v == e[j].u);
  return f[i] + W(e[i].t, e[j].s, C[e[i].v]);
}

void ins (int i) {
  int v = e[i].v;
  if (g[v].empty()) {
    return;
  }
  while (!stk[v].empty() && calc(stk[v].back().p, g[v][stk[v].back().l]) > calc(i, g[v][stk[v].back().l])) {
    stk[v].pop_back();
  }
  if (stk[v].empty()) {
    stk[v].eb((tup){i, 0, sz(g[v]) - 1});
  } else {
    int l = stk[v].back().l, r = stk[v].back().r + 1;
    while (l < r) {
      int md = (l + r) >> 1;
      calc(stk[v].back().p, g[v][md]) > calc(i, g[v][md]) ? r = md : l = md + 1;
    }
    if (l < sz(g[v])) {
      stk[v].eb((tup){i, l, sz(g[v]) - 1});
    }
  }
}

LL main () {
  L (i, 1, m) {
    d[++K] = e[i].s;
    d[++K] = e[i].t;
  }
  L (i, 1, q) {
    d[++K] = lp[i];
    d[++K] = rp[i];
  }
  sort(d + 1, d + K + 1);
  K = unique(d + 1, d + K + 1) - d - 1;
  auto get = [&] (int x) {
    return lower_bound(d + 1, d + K + 1, x) - d;
  };
  L (i, 1, m) {
    e[i].s = get(e[i].s);
    e[i].t = get(e[i].t);
  }
  L (i, 1, q) {
    lp[i] = get(lp[i]);
    rp[i] = get(rp[i]);
    lis[rp[i]].eb(lp[i]);
  }
  L (i, 1, K) {
    rt[i] = rt[i - 1];
    for (int x : lis[i]) {
      ins(x, 1, K, rt[i]);
    }
  }
  me(f, 0x3f);
  f[0] = 0;
  e[0].v = 1;
  sort(e + 1, e + m + 1, [] (edg a, edg b) {
    return a.t < b.t;
  });
  L (i, 0, m) {
    g[e[i].u].eb(i);
    atom[e[i].v].eb(i);
  }
  L (i, 1, n) {
    sort(g[i].begin(), g[i].end(), [] (int x, int y) {
      return e[x].s < e[y].s;
    });
    L (j, 0, sz(g[i]) - 1) {
      id[g[i][j]] = j;
    }
  }
  ins(0);
  L (i, 1, m) {
    int u = e[i].u;
    if (atom[u].empty() || stk[u].empty()) {
      continue;
    }
    int l = 0, r = sz(stk[u]) - 1;
    while (l < r) {
      int md = (l + r + 1) >> 1;
      stk[u][md].l <= id[i] ? l = md : r = md - 1;
    }
    f[i] = min(f[i], calc(stk[u][l].p, i) + e[i].w);
    ins(i);
  }
  LL ans = INF;
  for (int i : atom[n]) {
    ans = min(ans, f[i] + W(e[i].t, K + 1, C[n]));
  }
  return ans > 1e17 ? -1 : ans;
}

}

LL solve (int N, int M, int W, vi T, vi X, vi Y, vi A, vi B, vi C, vi L, vi R) {
  whq::n = N;
  whq::m = M;
  whq::q = W;
  L (i, 1, N) {
    whq::C[i] = T[i - 1];
  }
  L (i, 0, M - 1) {
    whq::e[i + 1] = {X[i] + 1, Y[i] + 1, C[i], A[i], B[i]};
  }
  L (i, 0, W - 1) {
    whq::lp[i + 1] = L[i];
    whq::rp[i + 1] = R[i];
  }
  return whq::main();
}

// int main () {
//   ios::sync_with_stdio(0), cin.tie(0);
//   int N, M, W;
//   cin >> N >> M >> W;
//   vi T(N);
//   vi X(M), Y(M), A(M), B(M), C(M);
//   vi L, R;
//   L.resize(W);
//   R.resize(W);
//   L (i, 0, N - 1) {
//     cin >> T[i];
//   }
//   L (i, 0, M - 1) {
//     cin >> X[i] >> Y[i] >> A[i] >> B[i] >> C[i];
//   }
//   L (i, 0, W - 1) {
//     cin >> L[i] >> R[i];
//   }
//   cout << solve(N, M, W, T, X, Y, A, B, C, L, R) << '\n';
// }
// I love WHQ!