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 MAX_N 100005
int N,M,si,ti;

struct edge {
  int to,fi,se;
};

vector< edge > G[MAX_N];

vector< vector< edge > > nG[MAX_N];

vector< int > g[MAX_N];
vector< int > d[MAX_N];

typedef pair< int ,int > P;
typedef pair< int , P > PP;

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

int dijkstra(){
  for(int i=0;i<N;i++){
    d[i].resize(g[i].size());
    for(int j=0;j<(int)d[i].size();j++)
      d[i][j]=1e9;
  }
  d[si][0]=0;
  priority_queue< PP , vector<PP> , greater<PP> > Q;
  Q.push( PP( 0 , P(si,0) ) );
  while(!Q.empty()){
    PP pp=Q.top();Q.pop();
    int pos=pp.second.first;
    int tm=pp.second.second;
    int cost=pp.first;
    if( d[pos][tm] < cost )continue;

    if( pos == ti )return cost;
    
    for(int i=0;i<(int)nG[pos][tm].size();i++){
      edge e=nG[pos][tm][i];
      int ntm=getId(e.to,e.se);

      if(d[e.to][ntm]>cost){
        d[e.to][ntm]=cost;
        Q.push(PP(cost,P(e.to,ntm)));
      }
      
    }

    if(tm+1==(int)g[pos].size())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;
}

int main(){
  scanf("%d %d %d %d",&N,&M,&si,&ti);
  si--,ti--;
  
  g[si].push_back(0);
  for(int i=0;i<M;i++){
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    a--,b--;
    
    G[a].push_back( (edge){b,c,c+d} );
    g[a].push_back(c);
    //    g[a].push_back(c+d);
    //    g[b].push_back(c);
    g[b].push_back(c+d);
  }

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

  for(int i=0;i<N;i++){
    nG[i].resize( g[i].size() );
    for(int j=0;j<(int)G[i].size();j++){
      edge e=G[i][j];
      int id=getId(i,e.fi);
      nG[i][id].push_back(e);
    }
  }

  printf("%d\n",dijkstra());
  return 0;
}