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;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;

const int V=100000;
const int N=404040;
const int INF=123456789;

set<int> TIMESET[V];
map<pi,int> v_to_id;

struct edge{int to,cost;};
vector<edge> G[N];
int dist[N];

int main()
{
    int n,m,s,g;
    scanf(" %d %d %d %d", &n, &m, &s, &g);
    --s;
    --g;

    TIMESET[s].insert(0);
    v_to_id[pi(s,0)] = 0;

    int idx=1;

    rep(i,m)
    {
        int u,v,t,c;
        scanf(" %d %d %d %d", &u, &v, &t, &c);
        --u;
        --v;

        TIMESET[u].insert(t);
        TIMESET[v].insert(t+c);

        if(v_to_id.find(pi(u,t)) == v_to_id.end()) v_to_id[pi(u,t)] = idx++;
        if(v_to_id.find(pi(v,t+c)) == v_to_id.end()) v_to_id[pi(v,t+c)] = idx++;

        int S=v_to_id[pi(u,t)], T=v_to_id[pi(v,t+c)];
        G[S].pb(edge{T,0});
    }

    rep(i,n)
    {
        int SZ = TIMESET[i].size();

        auto itr = TIMESET[i].begin();
        rep(j,SZ-1)
        {
            auto nx = itr;
            ++nx;

            int d = *nx - *itr;
            int S=v_to_id[pi(i,*itr)], T=v_to_id[pi(i,*nx)];
            G[S].pb(edge{T,d});

            ++itr;
        }
    }

    priority_queue<pi, vector<pi>, greater<pi>> pq;
    pq.push(pi(0,0));
    fill(dist,dist+N,INF);
    dist[0]=0;
    while(!pq.empty())
    {
        pi p=pq.top();
        pq.pop();
        int v=p.se;
        if(dist[v]<p.fi) continue;
        for(edge &e:G[v])
        {
            if(dist[e.to] > dist[v]+e.cost)
            {
                dist[e.to] = dist[v]+e.cost;
                pq.push(pi(dist[e.to],e.to));
            }
        }
    }

    int ans=INF;
    for(const auto &x:TIMESET[g])
    {
        int S = v_to_id[pi(g,x)];
        ans = min(ans,dist[S]);
    }
    printf("%d\n", ans);
    return 0;
}