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;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}


int N,M,orig,dest;

vector<int>lis[111111];

const int INF=1001001001;
vector<int>dp[111111];

vector<tuple<int,int,int>>ev[222222];
vector<int>latte[222222];
signed main(){
    cin>>N>>M>>orig>>dest;
    orig--;dest--;

    lis[orig].pb(0);

    latte[0].pb(orig);
    rep(i,M){
        int a,b,t,c;
        scanf("%lld%lld%lld%lld",&a,&b,&t,&c);
        a--;b--;
        latte[t].pb(a);
        latte[t+c].pb(b);

        lis[a].pb(t);
        lis[b].pb(t+c);
        ev[t].pb(make_tuple(a,b,c));
    }

    rep(i,N){
        sort(all(lis[i]));
        lis[i].erase(unique(all(lis[i])),lis[i].end());
    }

    rep(i,N){
        dp[i]=vint(lis[i].size(),INF);
    }
    dp[orig][0]=0;
    for(int t=0;t<222222;t++){
        for(auto w:latte[t]){
            int k=lower_bound(all(lis[w]),t)-lis[w].begin();
            if(k+1!=lis[w].size()){
                chmin(dp[w][k+1],dp[w][k]+lis[w][k+1]-lis[w][k]);
            }
        }

        for(auto &w:ev[t]){
            int a,b,c;
            tie(a,b,c)=w;

            int k=lower_bound(all(lis[a]),t)-lis[a].begin();
            int l=lower_bound(all(lis[b]),t+c)-lis[b].begin();
            chmin(dp[b][l],dp[a][k]);
        }
    }

    int ans=INF;
    rep(i,lis[dest].size())chmin(ans,dp[dest][i]);
    cout<<ans<<endl;
    return 0;
}