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 <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
#define int long long
struct Edge {
  int a, b, s, t, cost;
  Edge() {}
  Edge(int a_, int b_, int s_, int t_, int cost_) : a(a_), b(b_), s(s_), t(t_), cost(cost_) {}
};
struct State {
  int v, t, cost;
  State(int v_, int t_, int cost_) : v(v_), t(t_), cost(cost_) {}
  bool operator >(const State &other) const {
    return cost > other.cost;
  }
};
signed main() {
  int N, M, S, T; cin >> N >> M >> S >> T;
  S--, T--;
  vector<Edge> E(M);
  REP(i,M) {
    cin >> E[i].a >> E[i].b >> E[i].s >> E[i].t;
    E[i].a--;
    E[i].b--;
    E[i].t += E[i].s;
    E[i].cost = 0;
  }
  vector<vector<int>> TIME(N);
  TIME[S].push_back(0);
  REP(i,M) {
    TIME[E[i].a].push_back(E[i].s);
    TIME[E[i].b].push_back(E[i].t);
  }
  vector<map<int, vector<Edge>>> G(N);
  REP(i,N) {
    sort(TIME[i].begin(), TIME[i].end());
    REP(j,(int)TIME[i].size()-1) {
      if(TIME[i][j] != TIME[i][j+1]) {
        G[i][TIME[i][j]].emplace_back(i, i, TIME[i][j], TIME[i][j+1], TIME[i][j+1] - TIME[i][j]);
      }
    }
  }
  REP(i,M) {
    G[E[i].a][E[i].s].push_back(E[i]);
  }
  //REP(i,N) {
  //  for(const pair<int, vector<Edge>> &pp : G[i]) {
  //    for(const Edge &e : pp.second) {
  //      cerr << e.a << " => " << e.b << " (" << e.s << "," << e.t << ") C=" << e.cost << endl;
  //    }
  //  }
  //}
  vector<map<int, int>> D(N);
  priority_queue<State, vector<State>, greater<State>> Q;
  Q.emplace(S, 0, 0);
  D[S][0] = 0;
  while(!Q.empty()) {
    State s = Q.top(); Q.pop();
    if(D[s.v].count(s.t) && s.cost > D[s.v][s.t]) continue;
    for(const Edge &e : G[s.v][s.t]) {
      if((D[e.b].count(e.t) == 0) || (D[e.b][e.t] > s.cost + e.cost)) {
        D[e.b][e.t] = s.cost + e.cost;
        Q.emplace(e.b, e.t, D[e.b][e.t]);
      }
    }
  }
  int ans = (int)1e18;
  for(pair<int, int> iter : D[T]) {
    ans = min(ans, iter.second);
  }
  cout << ans << endl;
}