// Задача AT5 — МУХЪЛ
// Решение за подзадача 4 (без ограничения).  Сложност: O(M log M).
//
// Едно пръскане a може да „предаде границата“ на пръскане b, ако излекуваните им зони
// се застъпват въпреки настъпващия между дните им мухъл, т.е. при
//     left[b] <= right[a] - |day[a] - day[b]| + 1.
// Свеждаме задачата до най-къс път: целта е да свържем пръскане, покриващо участък 1,
// с пръскане, покриващо участък N.  След завъртане на 45 градуса (координати
// X = left - day и Y = left + day) достижимите от a пръскания b са тези с
//     X[b] <= right[a] - day[a] + 1   и   Y[b] <= right[a] + day[a] + 1,
// т.е. лежат в правоъгълна област.  Понеже всички ребра, влизащи в дадено пръскане b,
// имат еднаква цена cost[b], при Дейкстра всяко пръскание се установява окончателно
// веднъж.  За да добавяме наведнъж рёбра към всички пръскания в правоъгълна област,
// използваме персистентно дърво за интервали над пръсканията, подредени по X (и по Y),
// чиито възли служат за междинни върхове в графа.
//
// Бележка за имената: numSprays = броят пръскания (M), numCells = броят участъци (N).

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

namespace {

const int MAX_SPRAYS = 100000 + 10;
const llong INF = 1e18;

int numSprays;   // брой пръскания (M)
int numCells;    // брой участъци (N)

struct Spray {
    int day, left, right, cost;
    bool operator<(const Spray& other) const { return day < other.day; }
};
Spray sprays[MAX_SPRAYS];

// Граф: за всяко пръскане -- неговите изходящи ребра (връх, цена).
std::vector<std::pair<int, llong>> sprayEdges[MAX_SPRAYS];
// Ребрата на междинните възли от дървото (всеки възел има две деца).
std::pair<int, llong> treeEdges[40 * MAX_SPRAYS][2];
int nodeCounter;

// Персистентно дърво за интервали над пръскания, подредени по дадена координата.
// Възлите образуват йерархия от междинни върхове; листата сочат към пръсканията.
struct PersistentSegmentTree {
    struct Node { int graphNode, left, right; llong edgeCost; };
    Node tree[MAX_SPRAYS * 20];
    int root, size;

    void build(int lo, int hi, int node, int order[]) {
        if (lo == hi) {
            tree[node].graphNode = order[lo];
            tree[node].edgeCost = INF;
            return;
        }
        int mid = (lo + hi) / 2;
        tree[node].left = ++size;
        tree[node].right = ++size;
        build(lo, mid, tree[node].left, order);
        build(mid + 1, hi, tree[node].right, order);
        tree[node].graphNode = ++nodeCounter;
        tree[node].edgeCost = 0;
        treeEdges[tree[node].graphNode][0] = {tree[tree[node].left].graphNode,  tree[tree[node].left].edgeCost};
        treeEdges[tree[node].graphNode][1] = {tree[tree[node].right].graphNode, tree[tree[node].right].edgeCost};
    }

    void update(int lo, int hi, int newNode, int oldNode, int pos, int cost) {
        tree[newNode] = tree[oldNode];
        if (lo == hi) {
            tree[newNode].edgeCost = cost;
            return;
        }
        int mid = (lo + hi) / 2;
        if (pos <= mid) {
            tree[newNode].left = ++size;
            update(lo, mid, tree[newNode].left, tree[oldNode].left, pos, cost);
        } else {
            tree[newNode].right = ++size;
            update(mid + 1, hi, tree[newNode].right, tree[oldNode].right, pos, cost);
        }
        tree[newNode].graphNode = ++nodeCounter;
        treeEdges[tree[newNode].graphNode][0] = {tree[tree[newNode].left].graphNode,  tree[tree[newNode].left].edgeCost};
        treeEdges[tree[newNode].graphNode][1] = {tree[tree[newNode].right].graphNode, tree[tree[newNode].right].edgeCost};
    }

    // Добавя ребро от пръскане from към всички пръскания в интервала [ql, qr].
    void addEdges(int lo, int hi, int node, int ql, int qr, int from) {
        if (ql <= lo && hi <= qr) {
            sprayEdges[from].push_back({tree[node].graphNode, tree[node].edgeCost});
            return;
        }
        int mid = (lo + hi) / 2;
        if (ql <= mid)     addEdges(lo, mid, tree[node].left, ql, qr, from);
        if (mid + 1 <= qr) addEdges(mid + 1, hi, tree[node].right, ql, qr, from);
    }

    void build(int order[]) {
        root = 1;
        size = 1;
        build(1, numSprays, root, order);
    }
    void update(int pos, int cost) {
        int newRoot = ++size;
        update(1, numSprays, newRoot, root, pos, cost);
        root = newRoot;
    }
    void addEdges(int lo, int hi, int from) {
        addEdges(1, numSprays, root, lo, hi, from);
    }
};

bool settled[40 * MAX_SPRAYS];
llong dist[40 * MAX_SPRAYS];
PersistentSegmentTree treeByX, treeByY;
std::priority_queue<std::pair<llong, int>> queue;
int orderX[MAX_SPRAYS], orderY[MAX_SPRAYS], rankX[MAX_SPRAYS], rankY[MAX_SPRAYS];

llong shortestPath() {
    std::sort(sprays + 1, sprays + 1 + numSprays);

    // Подреждания по двете завъртяни координати X = left - day и Y = left + day.
    std::iota(orderX + 1, orderX + 1 + numSprays, 1);
    std::iota(orderY + 1, orderY + 1 + numSprays, 1);
    std::sort(orderX + 1, orderX + 1 + numSprays, [&](int x, int y) {
        return sprays[x].left + sprays[x].day < sprays[y].left + sprays[y].day;
    });
    std::sort(orderY + 1, orderY + 1 + numSprays, [&](int x, int y) {
        return sprays[x].left - sprays[x].day < sprays[y].left - sprays[y].day;
    });
    for (int i = 1; i <= numSprays; i++) {
        rankX[orderX[i]] = i;
        rankY[orderY[i]] = i;
    }

    nodeCounter = numSprays;

    // Първото дърво обслужва ограничението по координата X.
    treeByX.build(orderX);
    for (int i = numSprays; i >= 1; i--) {
        // намираме докъде стигат пръсканията с X в допустимия диапазон
        int lo = 0, hi = numSprays + 1;
        while (lo < hi - 1) {
            int mid = (lo + hi) / 2;
            if (sprays[orderX[mid]].left + sprays[orderX[mid]].day <= sprays[i].right + sprays[i].day + 1) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        if (lo != 0) treeByX.addEdges(1, lo, i);
        treeByX.update(rankX[i], sprays[i].cost);
    }

    // Второто дърво обслужва ограничението по координата Y.
    treeByY.build(orderY);
    for (int i = 1; i <= numSprays; i++) {
        int lo = 0, hi = numSprays + 1;
        while (lo < hi - 1) {
            int mid = (lo + hi) / 2;
            if (sprays[orderY[mid]].left - sprays[orderY[mid]].day <= sprays[i].right - sprays[i].day + 1) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        if (lo != 0) treeByY.addEdges(1, lo, i);
        treeByY.update(rankY[i], sprays[i].cost);
    }

    // Дейкстра: изворите са пръсканията, които покриват участък 1.
    llong answer = INF;
    std::fill(dist + 1, dist + 1 + nodeCounter, INF);
    for (int i = 1; i <= numSprays; i++) {
        if (sprays[i].left == 1) {
            dist[i] = sprays[i].cost;
            queue.push({-dist[i], i});
        }
    }
    while (!queue.empty()) {
        auto [d, node] = queue.top();
        queue.pop();
        if (node <= numSprays && sprays[node].right == numCells) {
            answer = dist[node];
            break;
        }
        if (settled[node]) continue;
        settled[node] = true;

        const auto& neighbours = (node <= numSprays)
            ? sprayEdges[node]
            : std::vector<std::pair<int, llong>>(treeEdges[node], treeEdges[node] + 2);
        for (const auto& [next, cost] : neighbours) {
            if (dist[next] > dist[node] + cost) {
                dist[next] = dist[node] + cost;
                queue.push({-dist[next], next});
            }
        }
    }
    return answer == INF ? -1 : answer;
}

}  // namespace

long long min_cost(int N, std::vector<int> T, std::vector<int> L,
                   std::vector<int> R, std::vector<int> C) {
    numCells = N;
    numSprays = (int)T.size();
    for (int i = 1; i <= numSprays; i++) {
        sprays[i] = {T[i - 1], L[i - 1], R[i - 1], C[i - 1]};
    }
    // нулиране на глобалното състояние (в случай на повторно извикване)
    for (int i = 1; i <= numSprays; i++) {
        sprayEdges[i].clear();
    }
    std::fill(settled, settled + 40 * MAX_SPRAYS, false);
    return shortestPath();
}
