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 all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

#define MAX_N 100000

struct edge {
  int to, dep, cost;
  edge(){}
  edge(int to, int dep, int cost):to(to), dep(dep), cost(cost){}
};

struct stat {
  int now, ela, wet;
  stat(){}
  stat(int now, int ela, int wet):now(now), ela(ela), wet(wet){}
  bool operator < (const stat s) const {
    return wet > s.wet;
  }
};

int N, M, S, G;
vector<edge> graph[MAX_N];
map<pint, int> mincost;

int dijkstra() {
  priority_queue<stat> que;
  mincost[make_pair(S, 0)] = 0;
  que.emplace(S, 0, 0);
  while(que.size()) {
    stat s = que.top(); que.pop();
    int now = s.now, ela = s.ela, wet = s.wet;
    pint p = make_pair(now, ela);
    if(now == G) return wet;
    if(mincost.count(p) && mincost[p] < wet) continue;
    for(edge& e : graph[now]) {
      pint q = make_pair(e.to, e.dep + e.cost);
      if(ela <= e.dep && (!mincost.count(q) || mincost[p] + e.dep - ela < mincost[q])) {
	mincost[q] = mincost[p] + e.dep - ela;
	que.emplace(e.to, e.dep + e.cost, mincost[q]);
      }
    }
  }
  return -1;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> N >> M >> S >> G;
  --S, --G;
  rep(i, M) {
    int u, v, t, c;
    cin >> u >> v >> t >> c;
    --u, --v;
    graph[u].emplace_back(v, t, c);
  }
  cout << dijkstra() << endl;

  return 0;
}