// Задача AT5 — МУХЪЛ
// Решение за подзадача 2 (M <= 16).  Сложност: O(2^M * M^2).
//
// Пробваме всички подмножества от пръскания. Дадено подмножество чисти дъската, ако
// сред избраните има верига от пръскане, покриващо участък 1, до пръскане, покриващо
// участък N, в която съседните се застъпват: пръскане a достига b при
// L[b] <= R[a] - |T[a]-T[b]| + 1. Взимаме чистещото подмножество с минимална сума.

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

namespace {
const int MAXM = 20;
bool reachable[MAXM];
int stackBuf[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;
    };
    const llong INF = 1e18;
    llong answer = INF;

    for (int mask = 1; mask < (1 << M); mask++) {
        for (int i = 0; i < M; i++) reachable[i] = false;
        int top = 0;
        for (int i = 0; i < M; i++)
            if ((mask >> i & 1) && L[i] == 1) { reachable[i] = true; stackBuf[top++] = i; }
        while (top > 0) {
            int a = stackBuf[--top];
            for (int b = 0; b < M; b++)
                if ((mask >> b & 1) && !reachable[b] && reaches(a, b)) {
                    reachable[b] = true;
                    stackBuf[top++] = b;
                }
        }
        bool clears = false;
        for (int i = 0; i < M; i++) if (reachable[i] && R[i] == N) clears = true;
        if (!clears) continue;

        llong cost = 0;
        for (int i = 0; i < M; i++) if (mask >> i & 1) cost += C[i];
        answer = std::min(answer, cost);
    }
    return answer >= INF ? -1 : answer;
}
