// Задача AT5 — МУХЪЛ
// Решение за подзадача 3 (M <= 5000).  Сложност: O(M^2 log M).
//
// Най-къс път: връх = пръскане, ребро a -> b с цена C[b], ако
// L[b] <= R[a] - |T[a]-T[b]| + 1. Изворите са пръсканията с L = 1, целта е R = N.

#include "mold.h"
#include <algorithm>
#include <vector>
#include <queue>
using llong = long long;

namespace {
const int MAXM = 5000 + 10;
const llong INF = 1e18;
llong dist[MAXM];
}

long long min_cost(int N, std::vector<int> T, std::vector<int> L,
                   std::vector<int> R, std::vector<int> C) {
    int M = (int)T.size();
    auto reaches = [&](int a, int b) {
        return (llong)L[b] <= (llong)R[a] - std::abs(T[a] - T[b]) + 1;
    };

    for (int i = 0; i < M; i++) dist[i] = INF;
    std::priority_queue<std::pair<llong, int>, std::vector<std::pair<llong, int>>, std::greater<>> pq;
    for (int i = 0; i < M; i++) if (L[i] == 1) { dist[i] = C[i]; pq.push({dist[i], i}); }

    llong answer = INF;
    while (!pq.empty()) {
        auto [d, a] = pq.top(); pq.pop();
        if (d > dist[a]) continue;
        if (R[a] == N) { answer = std::min(answer, d); continue; }
        for (int b = 0; b < M; b++)
            if (dist[b] > d + C[b] && reaches(a, b)) { dist[b] = d + C[b]; pq.push({dist[b], b}); }
    }
    return answer >= INF ? -1 : answer;
}
