#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i64 = long long;
using i128 = __int128;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<std::pair<int, int>, null_type, less<std::pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_pair;

typedef tree<i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_64;
typedef tree<std::pair<i64, i64>, null_type, less<std::pair<i64, i64>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_pair_64;

std::istream& operator>>(std::istream& iss, i128& n) {
    std::string s;
    iss >> s;
    n = 0;

    for (int i = (s[0] == '-'); i < s.size(); i++) {
        n = n * 10 + (s[i] - '0');
    }

    if (s[0] == '-') n = -n;
    return iss;
}

std::ostream& operator<<(std::ostream& oss, i128 n) {
    if (n == 0) return oss << "0";

    std::string s;
    if (n < 0) {
        s += '-';
        n = -n;
    }

    while (n) {
        s += '0' + n % 10;
        n /= 10;
    }

    std::reverse(s.begin() + (s[0] == '-'), s.end());
    return oss << s;
}

static const long long pow2[] = { 
    1LL, 2LL, 4LL, 8LL, 16LL, 32LL, 64LL, 128LL, 256LL, 512LL, 1024LL, 2048LL, 4096LL, 8192LL, 16384LL, 32768LL, 65536LL, 131072LL, 262144LL, 524288LL, 1048576LL, 2097152LL, 4194304LL, 8388608LL, 16777216LL, 33554432LL, 67108864LL, 134217728LL, 268435456LL, 536870912LL, 1073741824LL, 2147483648LL, 4294967296LL, 8589934592LL, 17179869184LL, 34359738368LL, 68719476736LL, 137438953472LL, 274877906944LL, 549755813888LL, 1099511627776LL, 2199023255552LL, 4398046511104LL, 8796093022208LL, 17592186044416LL, 35184372088832LL, 70368744177664LL, 140737488355328LL, 281474976710656LL, 562949953421312LL, 1125899906842624LL, 2251799813685248LL, 4503599627370496LL, 9007199254740992LL, 18014398509481984LL, 36028797018963968LL, 72057594037927936LL, 144115188075855872LL, 288230376151711744LL, 576460752303423488LL
};
static const long long pow3[] = {
    1LL, 3LL, 9LL, 27LL, 81LL, 243LL, 729LL, 2187LL, 6561LL, 19683LL, 59049LL, 177147LL, 531441LL, 1594323LL, 4782969LL, 14348907LL, 43046721LL, 129140163LL, 387420489LL, 1162261467LL, 3486784401LL, 10460353203LL, 31381059609LL, 94143178827LL, 282429536481LL, 847288609443LL, 2541865828329LL, 7625597484987LL, 22876792454961LL, 68630377364883LL, 205891132094649LL, 617673396283947LL, 1853020188851841LL, 5559060566555523LL, 16677181699666569LL, 50031545098999707LL, 150094635296999121LL, 450283905890997363LL
};
static const long long pow5[] = {
    1LL, 5LL, 25LL, 125LL, 625LL, 3125LL, 15625LL, 78125LL, 390625LL, 1953125LL, 9765625LL, 48828125LL, 244140625LL, 1220703125LL, 6103515625LL, 30517578125LL, 152587890625LL, 762939453125LL, 3814697265625LL, 19073486328125LL, 95367431640625LL, 476837158203125LL, 2384185791015625LL, 11920928955078125LL, 59604644775390625LL, 298023223876953125LL, 1490116119384765625LL
};
static const long long pow10[] = {
    1LL, 10LL, 100LL, 1000LL, 10000LL, 100000LL, 1000000LL, 10000000LL, 100000000LL, 1000000000LL, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL, 1000000000000000000LL
};

const i64 MOD1 = 1e9 + 7;
const i64 MOD2 = 998244353;
const i64 LARGE = 1e17;

void cf(bool value) {
    if (value) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

void atc(bool value) {
    if (value) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
}

/**
 * usage:
 * unordered_set<i64, custom_hash>
 * unordered_map<i64, i64, custom_hash>
 * // problem: https://atcoder.jp/contests/abc448/tasks/abc448_d
 */
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t RANDOM =
            std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + RANDOM);
    }
};

/**
 * usage:
 * unordered_set<pair<i64, i64>, pair_hash<i64, i64>>
 */
template<class T, class U>
struct pair_hash {
    size_t operator()(const std::pair<T,U>& p) const {
        uint64_t h1 = custom_hash::splitmix64((uint64_t)p.first);
        uint64_t h2 = custom_hash::splitmix64((uint64_t)p.second);
        return custom_hash::splitmix64(h1 ^ (h2 << 1));
    }
};

/**
 * usage:
 * unordered_set<vector<i64>, vector_hash<i64>>
 * // problem: https://codeforces.com/contest/1980/problem/E
 * 
 * unordered_map<vector<int>, int, vector_hash<int>>
 * // problem: https://atcoder.jp/contests/abc361/tasks/abc361_d
 */

template<class T>
struct vector_hash {
    size_t operator()(const std::vector<T>& v) const {
        static const uint64_t RANDOM =
            std::chrono::steady_clock::now().time_since_epoch().count();

        uint64_t h = RANDOM;
        for (auto &x : v) {
            uint64_t y = custom_hash::splitmix64((uint64_t)x);
            h = custom_hash::splitmix64(h ^ y);
        }

        return h;
    }
};

/**
 * usage:
 * unordered_set<tuple<int,int,int>, tuple_hash>
 */
struct tuple_hash {
    template<class... T>
    size_t operator()(const std::tuple<T...>& t) const {
        return apply([](const auto&... args) {
            uint64_t h = 0;
            ((h = custom_hash::splitmix64(h ^
                custom_hash::splitmix64((uint64_t)args))), ...);
            return h;
        }, t);
    }
};

struct DSU {
    std::vector<i64> par, sz, color;

    // 1-based indexing
    DSU(i64 n) {
        par.resize(n + 1, 0LL); 
        sz.resize(n + 1, 1LL);
        color.resize(n + 1, 0LL);
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            color[i] = i;
        }
    }

    // find the parent of x's component
    i64 find(i64 x) {
        while (x != par[x]) {
            x = par[x] = par[par[x]];
        }
        return x;
    }

    // to get the size of component x belongs to
    i64 size(i64 x) {
        x = find(x);
        return sz[x];
    }

    // check if x and y are in same component
    bool same(i64 x, i64 y) {
        return find(x) == find(y);
    }

    // merge components of x and y
    bool merge(i64 x, i64 y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) std::swap(x, y);
        par[y] = x;
        sz[x] += sz[y];
        return true;
    }

    bool merge_without_swap(i64 x, i64 y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        par[y] = x;
        sz[x] += sz[y];
        return true;
    }
};

struct HopcroftKarp {
    static constexpr i64 INF = LLONG_MAX / 4;
    
    // computing maximum bipartite matching
    i64 n, m;
    std::vector<std::vector<i64>> adj;
    std::vector<i64> dist, matchL, matchR;

    // 1-based indexing
    HopcroftKarp(i64 n, i64 m): n(n), m(m) {
        adj.assign(n + 1, {});
        matchL.assign(n + 1, -1);
        matchR.assign(m + 1, -1);
        dist.resize(n + 1);
    }

    void add(i64 u, i64 v) {
        adj[u].push_back(v);
    }

    bool bfs() {
        std::queue<i64> q;
        bool found = false;

        for (int i = 1; i <= n; i++) {
            if (matchL[i] == -1) {
                dist[i] = 0LL;
                q.push(i);
            } else {
                dist[i] = INF;
            }
        }

        while (!q.empty()) {
            i64 u = q.front(); q.pop();
            for (auto v: adj[u]) {
                i64 nxt = matchR[v];
                if (nxt != -1 && dist[nxt] == INF) {
                    dist[nxt] = dist[u] + 1;
                    q.push(nxt);
                }
                if (nxt == -1) {
                    found = true;
                }
            }
        }
        return found;
    }

    bool dfs(i64 u) {
        for (auto v: adj[u]) {
            i64 nxt = matchR[v];
            if (nxt == -1 || (dist[nxt] == dist[u] + 1 && dfs(nxt))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = INF;
        return false;
    }

    // use this to get the size of the matching
    i64 compute_size() {
        i64 matching = 0LL;
        while (bfs()) {
            for (int i = 1; i <= n; i++) {
                if (matchL[i] == -1 && dfs(i)) {
                    matching++;
                }
            }
        }
        return matching;
    }

    // use this to get the list of matched edges in matching
    std::vector<std::array<i64, 2>> matching_edges() {
        std::vector<std::array<i64, 2>> edges;
        for (i64 u = 1; u <= n; u++) {
            if (matchL[u] != -1) {
                edges.push_back({u, matchL[u]});
            }
        }
        return edges;
    }

    // konigs theorem
    std::array<std::vector<i64>, 2> minimum_vertex_cover() {
        std::vector<bool> visL(n + 1, false), visR(m + 1, false);
        std::queue<i64> q;

        for (i64 u = 1; u <= n; u++) {
            if (matchL[u] == -1) {
                q.push(u);
                visL[u] = true;
            }
        }

        while (!q.empty()) {
            i64 u = q.front(); q.pop();
            for (auto v: adj[u]) {
                if (matchL[u] != v && !visR[v]) {
                    visR[v] = true;

                    if (matchR[v] != -1 && !visL[matchR[v]]) {
                        visL[matchR[v]] = true;
                        q.push(matchR[v]);
                    }
                }
            }
        }

        std::vector<i64> coverL, coverR;
        for (i64 u = 1; u <= n; u++) {
            if (!visL[u]) coverL.push_back(u);
        }

        for (i64 v = 1; v <= m; v++) {
            if (visR[v]) coverR.push_back(v);
        }

        return {coverL, coverR};
    }
};

const i64 SIEVE_MAX = 1e9;
const i64 SIEVE_SQRT = 1e6;
 
i64 lp[SIEVE_SQRT + 1];
std::vector<i64> prs;
 
void init_sieve() {
    for (i64 i = 2; i <= SIEVE_SQRT; i++) {
        if (lp[i] == 0) {
            lp[i] = i;
            prs.push_back(i);
        }
        for (i64 j = 0; i * prs[j] <= SIEVE_SQRT; j++) {
            lp[i * prs[j]] = prs[j];
            if (prs[j] == lp[i]) break;
        }
    }
}
 
i64 binpow(i64 x, i64 y,i64 m) {
    x %= m;
    i64 result = 1;
 
    while (y > 0) {
        if (y & 1) result = result * x % m;
        x = x * x % m;
        y >>= 1;
    }
 
    result %= m;
    return result;
}
 
i64 modinv(i64 x, i64 p) {
    return binpow(x, p - 2, p);
}

struct Pascal {
    i64 N, M = -1;
    std::vector<std::vector<i64>> binom;

    Pascal(i64 N, i64 M = -1): N(N), M(M) {
        binom.resize(N + 1, std::vector<i64>(N + 1));
        compute();
    }

    void compute() {
        for (int i = 0; i <= N; i++) {
            binom[i][0] = 1;
            binom[i][i] = 1;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j < i; j++) {
                i64 ans = binom[i - 1][j] + binom[i - 1][j - 1];
                if (M != -1) ans %= M;
                binom[i][j] = ans;
            }
        }
    }   

    i64 C(i64 n, i64 k) {
        if (k < 0 || k > n) return 0;
        return binom[n][k];
    }
};

struct TrieNode {
    i64 count;
    TrieNode* link[26];
    TrieNode() {
        count = 0LL;
        for (int i = 0; i < 26; i++) {
            link[i] = nullptr;
        }
    }
};

struct Trie {
    TrieNode* root;
    Trie() {
        root = new TrieNode();
    }

    i64 add(std::string s) {
        i64 ans = 0;
        TrieNode* new_root = root;
        for (int i = 0; i < s.length(); i++) {
            if (new_root->link[s[i] - 'a'] == nullptr) {
                new_root->link[s[i] - 'a'] = new TrieNode();
            }
            new_root = new_root->link[s[i] - 'a'];
            ans += new_root->count;
            new_root->count++;
        }
        return ans;
    }
};

i64 isqrt(i64 x) {
    i64 r = sqrtl(x);
    while ((r + 1) * (r + 1) <= x) r++;
    while (r * r > x) r--;
    return r;
}

struct binomial {
    void copy() {
        i64 n;
        i64 fact[n + 1], invfact[n + 1];
        fact[0] = 1; invfact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (i * fact[i - 1]) % MOD2;
        }

        invfact[n] = modinv(fact[n], MOD2);
        for (int i = n - 1; i > 0; i--) {
            invfact[i] = (invfact[i + 1] * (i + 1)) % MOD2;
        }

        auto coeff = [&] (i64 x, i64 y) -> i64 {
            if (x < y || y < 0) return 0;
            i64 ans = 1;
            ans = (ans * fact[x]) % MOD2;
            ans = (ans * invfact[y]) % MOD2;
            ans = (ans * invfact[x - y]) % MOD2;
            return ans;
        };
    }
};

struct MergeSortTree {
    struct MergeSortNode {
        vector<i64> sorted; // sorted by x
        vector<i64> suff; // suff minima of y
    };

    i64 n;
    vector<MergeSortNode> a;
    MergeSortTree(i64 n, vector<i64>& tin, vector<i64>& tout): n(n) {
        a.resize(4 * n + 5);
        build_tree(tin, tout, 1, 1, n);
    }

    MergeSortNode combine(MergeSortNode n1, MergeSortNode n2) {
        MergeSortNode res;
        i64 l = 0, r = 0;
        while (l < n1.sorted.size() && r < n2.sorted.size()) {
            if (n1.sorted[l] < n2.sorted[r]) {
                res.sorted.push_back(n1.sorted[l++]);
            } else {
                res.sorted.push_back(n2.sorted[r++]);
            }
        }

        while (l < n1.sorted.size()) res.sorted.push_back(n1.sorted[l++]);
        while (r < n2.sorted.size()) res.sorted.push_back(n2.sorted[r++]);

        i64 len = res.sorted.size();
        res.suff.resize(len);
        res.suff[len - 1] = res.sorted[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            res.suff[i] = min(res.suff[i + 1], res.sorted[i]);
        }
        return res;
    }

    void build_tree(vector<i64>& tin, vector<i64>& tout, i64 v, i64 l, i64 r) {
        if (l == r) {
            a[v].sorted.push_back(tin[l]);
            a[v].suff.push_back(tout[l]);
            return;
        }

        i64 mid = (l + r) >> 1;
        build_tree(tin, tout, 2 * v, l, mid);
        build_tree(tin, tout, 2 * v + 1, mid + 1, r);
        a[v] = combine(a[2 * v], a[2 * v + 1]);
    }

    bool exists(MergeSortNode& res, i64 x, i64 y) {
        auto it = lower_bound(res.sorted.begin(), res.sorted.end(), x);
        if (it == res.sorted.end()) return false;

        i64 pos = it - res.sorted.begin();
        return res.suff[pos] <= y;
    }

    bool check(i64 x, i64 y, i64 l, i64 r, i64 v, i64 L, i64 R) {
        if (L > R || L > r || R < l) return false;
        if (l <= L && R <= r) {
            return exists(a[v], x, y);
        }

        i64 mid = (L + R) >> 1;
        if (check(x, y, l, r, 2 * v, L, mid)) return true;
        if (check(x, y, l, r, 2 * v + 1, mid + 1, R)) return true;
        return false;
    }

    bool check(i64 x, i64 y, i64 l, i64 r) {
        return check(x, y, l, r, 1, 1, n);
    }
};

struct Node {
    i64 val;
    Node(i64 v = 0): val(v) {}
    Node& operator=(i64 v) {
        val = v;
        return *this;
    }
    Node& operator+=(i64 v) {
        val += v;
        return *this;
    }
    Node& operator+=(const Node& other) {
        val += other.val;
        return *this;
    }
};

template <typename Merge>
struct IterativeSegtree {
    i64 N;
    vector<Node> tree;
    Merge merge;
    Node identity;

    IterativeSegtree(i64 n, const vector<i64>& a,
                    Merge merge,
                    Node identity): N(n), merge(merge), identity(identity) {
        tree.assign(2 * N, identity);
        construct(a);
    }

    void construct(const vector<i64>& a) {
        for (int i = 1; i <= N; i++) tree[i + N - 1] = a[i];
        for (int i = N - 1; i >= 1; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
    }

    // answer sum a[l, r)
    i64 query(i64 l, i64 r) {
        Node resl = identity, resr = identity;
        for (l += N - 1, r += N - 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tree[l++]);
            if (r & 1) resr = merge(tree[--r], resr);
        }
        return merge(resl, resr).val;
    }

    // set a[idx] = val
    void set(i64 idx, i64 val) {
        idx += N - 1;
        tree[idx] = val;
        for (idx >>= 1; idx > 0; idx >>= 1) {
            tree[idx] = merge(tree[idx << 1], tree[idx << 1 | 1]);
        }
    }

    // update a[idx] += val
    void update(i64 idx, i64 val) {
        idx += N - 1;
        tree[idx] += val;
        for (idx >>= 1; idx > 0; idx >>= 1) {
            tree[idx] = merge(tree[idx << 1], tree[idx << 1 | 1]);
        }
    }

    // find the first r >= l such that predicate is false on [l, r]
    i64 partition_point(i64 l, function<bool(const Node&)> pred) {
        Node pref = identity;
        i64 idx = l + N - 1;

        while (true) {
            while ((idx & 1) == 0) idx >>= 1;
            Node next = merge(pref, tree[idx]);
            if (!pred(next)) break;

            pref = next;
            idx++;

            if ((idx & (idx - 1)) == 0) return N + 1;
        }

        while (idx < N) {
            idx <<= 1;
            Node next = merge(pref, tree[idx]);
            if (pred(next)) {
                pref = next;
                idx++;
            }
        }

        return idx - (N - 1);
    }

    i64 find_first(i64 l, function<bool(i64)> pred) {
        return partition_point(l, [&](const Node& nd) {
            return pred(nd.val);
        });
    }
};  

// IterativeSegtree<RangeSum> tree(n, a, RangeSum(), Node(0));
struct RangeSum {
    Node operator()(const Node& a, const Node& b) const {
        return Node(a.val + b.val);
    }
};

// IterativeSegtree<RangeMin> tree(n, a, RangeMin(), Node(2e18));
struct RangeMin {
    Node operator()(const Node& a, const Node& b) const {
        return Node(min(a.val, b.val));
    }
};

// IterativeSegtree<RangeMax> tree(n, a, RangeMax(), Node(-2e18));
struct RangeMax {
    Node operator()(const Node& a, const Node& b) const {
        return Node(max(a.val, b.val));
    };
};

void debug_later() {
    i64 n, x, y;
    cin >> n >> x >> y;

    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    i64 ans = 0;
    IterativeSegtree<RangeMin> tree1(n, a, RangeMin(), Node(2e18));
    IterativeSegtree<RangeMax> tree2(n, a, RangeMax(), Node(-2e18));

    // https://atcoder.jp/contests/abc247/tasks/abc247_e
    for (int i = 1; i <= n; i++) {
        i64 lm = tree1.find_first(i, [&](i64 val) { return val > y; });
        i64 rm = tree1.find_first(i, [&](i64 val) { return val <= y; }) - 1;
        i64 lM = tree2.find_first(i, [&](i64 val) { return val < x; });
        i64 rM = tree2.find_first(i, [&](i64 val) { return val >= x; }) - 1;
        i64 L = max(lm, lM);
        i64 R = min(rm, rM);
        if (L > R) continue;
        ans += (R - L + 1);
    }
    cout << ans << '\n';
} 

/**
Mod Int template:
1. to be used for counting problems (problems with too many modular operations)
2. constructors:
  - default constructor
  - 1-arg constructor
3. modint functions:
  - plus, minus, multiplication operator (binary and assignment)
  - stream operators
 */
template <i64 Z>
struct modint {
private:
    static i64 norm(i64 x_val) {
        if (x_val < 0) {
            x_val += Z;
        }
        if (x_val >= Z) {
            x_val -= Z;
        }
        return x_val;
    }
    i64 power(i64 a, i64 b) const {
        i64 res = 1;
        for (; b; b /= 2, a = (a * a) % Z) {
            if (b % 2) {
                res = (res * a) % Z;
            }
        }
        return res;
    }

public:
    i64 x; // the actual number

    // modint constructors
    modint(): x(0) {}
    modint(i64 x_val): x(norm(x_val % Z)) {} 

    // modint functions
    // 1. unary negative
    modint operator-() const {
        return modint(norm(Z - x));
    }
    // 2. operation assignment
    modint& operator=(i64 val) {
        x = norm(val % Z);
        return *this;
    }
    modint& operator+=(const modint& other) {
        x = norm(x + other.x);
        return *this;
    }
    modint& operator+=(i64 val) {
        x = norm((x + val) % Z);
        return *this;
    }
    modint& operator-=(const modint& other) {
        x = norm(x - other.x);
        return *this;
    }
    modint& operator-=(i64 val) {
        x = norm((x - val) % Z);
        return *this;
    }
    modint& operator*=(const modint& other) {
        x = (x * other.x) % Z;
        return *this;
    }
    modint& operator*=(i64 val) {
        x = (x * (val % Z)) % Z;
        x = norm(x);
        return *this;
    }
    bool operator==(const modint& other) const {
        return x == other.x;
    }
    bool operator!=(const modint& other) const {
        return !(*this == other);
    }
    // 3. modular inverse
    modint inv() const {
        return modint(power(x, Z - 2));
    }
    modint& operator/=(const modint& other) {
        x = (x * other.inv().x) % Z;
        return *this;
    }
    // 4. binary operators
    friend modint operator+(modint first, const modint& second) {
        first += second;
        return first;
    }
    friend modint operator+(i64 val, modint first) {
        first += val;
        return first;
    }
    friend modint operator+(modint first, i64 val) {
        first += val;
        return first;
    }
    friend modint operator-(modint first, const modint& second) {
        first -= second;
        return first;
    }
    friend modint operator-(modint first, i64 val) {
        first -= val;
        return first;
    }
    friend modint operator*(modint first, const modint& second) {
        first *= second;
        return first;
    }
    friend modint operator*(modint first, i64 val) {
        first *= val;
        return first;
    }
    friend modint operator*(i64 val, modint first) {
        first *= val;
        return first;
    }
    friend modint operator/(modint first, const modint& second) {
        first /= second;
        return first;
    }
    // 5. stream operators
    friend std::istream& operator>>(std::istream& iss, modint& a) {
        i64 result;
        iss >> result;
        a = modint(result);
        return iss;
    }
    friend std::ostream& operator<<(std::ostream& oss, const modint& a) {
        return oss << a.x;
    }
};

using z1 = modint<MOD1>;
using z2 = modint<MOD2>;

void solve() {
    i64 n, c, v; cin >> n >> c >> v;
    vector<vector<array<i64, 3>>> adj(n + 1), adjr(n + 1);
    vector<i64> s(v + 1), t(v + 1), y(v + 1), m(v + 1);
    vector<i64> in(n + 1);
    for (int i = 1; i <= v; i++) cin >> s[i];
    for (int i = 1; i <= v; i++) cin >> t[i];
    for (int i = 1; i <= v; i++) cin >> y[i];
    for (int i = 1; i <= v; i++) cin >> m[i];
    for (int i = 1; i <= v; i++) {
        adjr[t[i]].push_back({s[i], y[i], m[i]}); // from, cost, time
        adj[s[i]].push_back({t[i], y[i], m[i]}); // to, cost, time
        in[t[i]]++;
    }

    i64 dp[n + 1][c + 1]; // dp[i][j] = minimum time to reach ith city in exactly j cost
    fill(&dp[0][0], &dp[0][0] + (n + 1)*(c + 1), 1e18);
    dp[1][0] = 0;

    vector<bool> vis(n + 1, false);
    queue<i64> q; q.push(1);
    while (q.size()) {
        auto f = q.front(); q.pop();
        for (auto [u, v, w]: adjr[f]) {
            if (vis[u]) continue;
            vis[u] = true;
            q.push(u);
        }
        if (f != 1) {
            for (auto [u, v, w]: adj[f]) {
                in[u]--;
            }
        }
    }

    in[1] = 0;
    q.push(1);
    while (q.size()) {
        auto f = q.front(); q.pop();
        for (auto [u, v, w]: adj[f]) {
            for (int i = 0; i + v <= c; i++) {
                if (dp[f][i] == 1e18) continue;
                dp[u][i + v] = min(dp[u][i + v], dp[f][i] + w);
            }

            in[u]--;
            if (in[u] == 0) {
                q.push(u);
            }
        }
    }

    i64 best = 1e18;
    for (int i = 0; i <= c; i++) {
        best = min(best, dp[n][i]);
    }

    if (best == 1e18) {
        cout << -1 << '\n';
    } else {
        cout << best << '\n';
    }
}

z2 checker(i64 n) {
    z2 ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            i64 rem = i * i - j;
            if (rem < 0) continue;
            i64 sq = isqrt(rem);
            if (sq * sq == rem) ans += 1;
        }
    }
    return ans;
}

void stress_test() {
    for (int i = 1; i <= 20; i++) {
        z2 checker_ans = checker(i);
        // z2 solver_ans = solve(i);
        // if (checker_ans != solver_ans) {
        //     cout << i << ' ' << checker_ans << ' ' << solver_ans << '\n';
        // }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t;

    // preprocessing
    // init_sieve();

    bool debug = false;
    bool stress = false;
    if (stress) {
        stress_test();
        return 0;
    }

    if (!debug) {
        while (t--) {
            solve();
        }
    } else {
        vector<pair<pair<i64, i64>, vector<i64>>> tests;
        for (int i = 0; i < t; i++) {
            i64 x, y;
            cin >> x >> y;
            pair<i64, i64> p = {x, y};
            vector<i64> a;
            for (int j = 1; j <= x; j++) {
                i64 z; cin >> z;
                a.push_back(z);
            }
            tests.push_back({p, a});
        }

        cout << tests[39].first.first << ' ' << tests[39].first.second << '\n';
        for (auto u: tests[39].second) {
            cout << u << ' ';
        }
    }
}