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;

int N,M;
int s,g;

struct state{
  int t,c,to;
  bool operator<(const state& st) const {
    return t < st.t;
  }
};
vector<state> U[200015];
vector<int> V[200015];
typedef pair<int,int> P;

map<P,int> ids;

struct edge {
  int to,c;
  edge(){
  }
  edge(int to,int c):to(to),c(c){}
  bool operator<(const edge& e) const {
    return c > e.c;
  }
};

vector<edge> G[400115];
vector<int> gs;
const int INF = (1<<29);
int H[400115];
int cnt;
int dijk(){
  fill( H,H+cnt+1,INF );
  priority_queue<edge> q;

  q.push( edge(ids[P(s,0)],0) );
  H[ids[P(s,0)]] = 0;

  while( !q.empty() ) {
    edge p = q.top(); q.pop();
    if( H[p.to] < p.c ) continue;
    for(edge e : G[p.to]){
      if( H[e.to] > p.c + e.c){
        H[e.to] = p.c + e.c;
        q.push( edge(e.to,p.c+e.c) );
      }
    }
  }
  int res = INF;
  for( int gg : gs ){
    res = min( res, H[gg] );
  }
  return res;
}

int main() {
  cin >> N >> M >> s >> g; --s; --g;
  cnt = 0;

  ids[P(s,0)] = cnt++;
  V[s].push_back(0);

  for(int i=0;i<M;i++){
    int u,v,t,c; cin >> u >> v >> t >> c; --u; --v;
    U[u].push_back( (state){t,c,v} );
    V[v].push_back( t+c );
    if( ids.count( P(v,t+c) ) == 0 ) {
      ids[P(v,t+c)] = cnt++;
    }
    if( v == g ) gs.push_back(ids[P(v,t+c)] );
  }


  for(int i=0;i<N;i++){
    sort( U[i].begin(), U[i].end() );
    sort( V[i].begin(), V[i].end() );
    V[i].erase( unique( V[i].begin(), V[i].end()), V[i].end() );

    for(int j=U[i].size()-1,k=V[i].size()-1;j>-1&&k>-1;j--){
      state su = U[i][j];
      int sv = V[i][k];
      while( sv > su.t) {
        k--; if( k<0 ) break;
        sv = V[i][k];
      }
      if( k < 0 ) break;
      int nu = ids[P(i,sv)];
      int nv = ids[P(su.to,su.t+su.c)];
      G[nu].emplace_back( nv, abs(su.t-sv) );
    }
    for(int j=V[i].size()-1;j>0;j--){
      int nv = ids[P(i,V[i][j])];
      int nu = ids[P(i,V[i][j-1])];
      G[nu].emplace_back( nv, abs(V[i][j]-V[i][j-1]));
    }

  }
  
/*
    for( auto id : ids) {
      cout << id.first.first << " "<< id.first.second << " = " << id.second << endl;
      for( edge e : G[id.second] ) {
        cout << " -> " << e.to<< " "<< e.c << endl;
      }
    }

*/
  cout << dijk() << endl;
}