Problem: problem

AOR Ika is at the $ S $ th bus stop at time $ 0 $ and wants to go from there to the $ G $ th bus stop. The number of bus stops $ N $ and $ M $ routes (*) connecting different bus stops are given. The bus stops are numbered $ 1, \ dots, and N $, respectively. Each route consists of $ 4 $ values: origin $ u $, destination $ v $, departure time $ t $, and travel time $ c $. You can catch the bus if you are at the departure $ u $ at the time $ t $ and arrive at the destination $ v $ at the time $ t + c $. While not on the bus, AOR Ika gets wet in the rain. When heading to the $ G $ th bus stop through the route that minimizes the time of getting wet in the rain, output the total time of getting wet in the rain from the time $ 0 $ to the arrival at the $ G $ th bus stop.

(*) In graph theory terms, a path is a sequence of vertices and edges, but please note that it is used here to mean edges.



input

Input is given from standard input in the following format.

$ N \ M \ S \ G $
$ u_1 \ v_1 \ t_1 \ c_1 $
$ \ vdots $
$ u_M \ v_M \ t_M \ c_M $

output

Print the minimum amount of time you get wet in one line. Also, output a line break at the end.

Example

Input

2 2 1 2
1 2 10 100
1 2 5 500


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

const bool debug = true;
#define dbg(...) if(debug) printf(__VA_ARGS__)
#define print(var) if (debug) cout << #var << " = " << var << endl

namespace {
    /** output whole vector. ex) vector<int>{1, 2, 3} -> '1 2 3'. */
    template<typename T>
    ostream& operator<<(ostream& os, const vector<T>& xs) {
       if (xs.empty()) return os << "[]";
       os << xs[0];
       for (auto i = 1; i < xs.size(); i++) os << ' ' << xs[i];
       return os;
    }
    template<typename K, typename V>
    ostream& operator<<(ostream& os, const pair<K, V>& p) {
        return os << "(" << p.first << "," << p.second << ")";
    }
    template<typename K, typename V>
    ostream& operator<<(ostream& os, const map<K, V>& m) {
        bool first = true;
        for (auto p : m) {
            if (first) first = false;
            else os << ":";
            os << "(" << p.first << "," << p.second << ")";
        }
        return os;
    }


    map<tuple<int, int, bool>, int> id;
    vector<tuple<int, int, bool>> fromId;

    struct Edge {
        int to, cost;
        Edge(int to, int cost) : to(to), cost(cost) {}
    };
    vector<vector<Edge>> Graph;

    int N, M, S, G;

    bool IN = false;
    bool OUT = true;

    void solve() {
        cin >> N >> M >> S >> G;
        S--; G--;
        vector<vector<tuple<int, int, bool>>> V(N);
        auto init = make_tuple(S, 0, IN);
        V[S].push_back(init);
        id[init] = 0;
        fromId.push_back(init);
        Graph.emplace_back();
        for (int  i = 0; i < M; i++) {
            int u, v, t, c; cin >> u >> v >> t >> c;
            u--; v--;
            auto x = make_tuple(u, t, OUT);
            auto x_id = id.count(x) ? id[x] : fromId.size();
            if (not id.count(x)) {
                fromId.push_back(x);
                id[x] = x_id;
                Graph.emplace_back();
            }
            V[u].push_back(x);
            auto y = make_tuple(v, t + c, IN);
            auto y_id = id.count(y) ? id[y] : fromId.size();
            if (not id.count(y)) {
                fromId.push_back(y);
                id[y] = y_id;
                Graph.emplace_back();
            }
            V[v].push_back(y);
            Graph[x_id].emplace_back(y_id, 0);
        }
        for (auto& L : V) {
            sort(L.begin(), L.end(), [&](const tuple<int, int, bool>& a, const tuple<int, int, bool>& b) {
                return get<1>(a) == get<1>(b) ? get<2>(a) < get<2>(b) : get<1>(a) < get<1>(b);
            });
            for (unsigned i = 0; i + 1 < L.size(); i++) {
                auto& x = L[i];
                auto& y = L[i + 1];
                auto time_x = get<1>(x);
                auto time_y = get<1>(y);
                Graph[id[x]].emplace_back(id[y], time_y - time_x);
            }
        }

        auto start = id[ V[S][0] ];

        // dijkstra
        const int INF = 1<<28;
        vector<int> D(Graph.size(), INF);
        struct State {
            int v, cost;
            State(int v, int cost) : v(v), cost(cost) {}
            bool operator<(const State& s) const {
                return cost > s.cost;
            }
        };
        priority_queue<State> PQ;
        PQ.emplace(start, 0);
        D[start] = 0;
        while (not PQ.empty()) {
            auto cur = PQ.top(); PQ.pop();
            for (auto& e : Graph[cur.v]) {
                auto next = e.to;
                if (D[next] > cur.cost + e.cost) {
                    D[next] = cur.cost + e.cost;
                    PQ.emplace(next, D[next]);
                }
            }
        }
        int ans = INF;
        for (auto& goal_vertex : V[G]) {
            auto goal = id[goal_vertex];
            ans = min(ans, D[goal]);
        }
        cout << ans << endl;
    }
}

int main() {
    solve();
    return 0;
}