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>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define fi first
#define se second
#define int long long
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;

struct edge{
    int to, l, r;
};

const int INF = 1e9;
int n, m, si, ti;
vector<edge> G[100010];
vector<int> g[100010], d[100010];
vector<vector<edge> > nG[100010];

int getid(int pos, int t){
    vector<int> :: iterator it;
    it = lower_bound(all(g[pos]), t);
    assert(g[pos].end() != it);
    assert(*it == t);
    return it - g[pos].begin();
}

int dijkstra(){
    rep(i, 0, n){
        d[i].resize(g[i].size());
        rep(j, 0, d[i].size()){
            d[i][j] = INF;
        }
    }
    priority_queue<PP, vector<PP>, greater<PP> > q;
    d[si][0] = 0;
    q.push(PP(0, P(si, 0)));

    while(!q.empty()){
        PP p = q.top(); q.pop();
        int pos = p.se.fi;
        int tm = p.se.se;
        int cost = p.fi;
        if(cost > d[pos][tm]) continue;
        if(pos == ti) return cost;

        rep(i, 0, nG[pos][tm].size()){
            edge e = nG[pos][tm][i];
            int ntm = getid(e.to, e.r);
            if(d[e.to][ntm] > cost){
                d[e.to][ntm] = cost;
                q.push(PP(cost, P(e.to, ntm)));
            }
        }
        if(tm == g[pos].size() - 1) continue;
        int ncost = cost + g[pos][tm + 1] - g[pos][tm];
        if(d[pos][tm + 1] > ncost){
            d[pos][tm + 1] = ncost;
            q. push(PP(ncost, P(pos, tm + 1)));
        }
    }
    assert(0);
    return -1;
}

signed main(){
    cin >> n >> m >> si >> ti;
    si--; ti--;
    g[si]. push_back(0);
    rep(i, 0, m){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--; b--;
        G[a]. push_back((edge){b, c, c + d});
        g[a]. push_back(c);
        g[b]. push_back(c + d);
    }
    rep(i, 0, n){
        sort(all(g[i]));
        g[i].erase(unique(all(g[i])), g[i].end());
    }
    rep(i, 0, n){
        nG[i].resize(g[i].size());
        rep(j, 0, G[i].size()){
            edge e = G[i][j];
            int id = getid(i, e.l);
            nG[i][id]. push_back(e);
        }
    }
    cout << dijkstra() << endl;
}