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,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define each(a,x) for(auto a : (x))
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) ((a) = min((a),(b)))
#define chmax(a,b) ((a) = max((a),(b)))
#define in_range(x,l,r) ((l)<=(x) && (x)<(r))
#define printvec(a) rep(i,a) cout << a[i] << " \n"[i+1==(a).size()];
#define fs first
#define sc second
#define em emplace
#define eb emplace_back
#define sz size()
#define MP make_pair
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;

const ll INF = 1e8;
const D EPS = 1e-8;
const ll MOD = 1e9+7;

struct edge{
  int u,v,s,t;
  edge(int a=0, int b=0, int x=0, int y=0):u(a), v(b), s(x), t(y) {}
  bool operator<(const edge &e) const {
    return t < e.t;
  }
};

int main(){
  int n,m,s,g;
  cin >> n >> m >> s >> g; s--; g--;

  vector<vi> event(n);
  vector<edge> edges;
  rep(i,m){
    int u,v,t,c;
    cin >> u >> v >> t >> c; u--; v--;
    edges.eb( edge(u,v,t,t+c) );
    event[v].eb(t+c);
  }
  event[s].eb(0);
  sort(all(edges));
  rep(i,n){
    sort(all(event[i]));
    event[i].erase( unique(all(event[i])), event[i].end() );
    //rep(j,event[i].size()) cerr << event[i][j] << " ";
    //cerr << endl;
  }

  vector<vi> ans(n);
  rep(i,n){
    if(i==g) ans[i] = vi(event[i].size(), 0);
    else ans[i] = vi(event[i].size(), INF);
  }

  rrep(i, m){
    edge &e = edges[i];
    int u_p = upper_bound(all(event[e.u]), e.s) - event[e.u].begin();
    int v_p = lower_bound(all(event[e.v]), e.t) - event[e.v].begin();

    if(u_p != 0) chmin(ans[e.u][u_p-1], ans[e.v][v_p] + (e.s - event[e.u][u_p-1]));
    if(v_p != 0) chmin(ans[e.v][v_p-1], ans[e.v][v_p] + event[e.v][v_p] - event[e.v][v_p-1]);
  }
  cout << ans[s][0] << endl;
}