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;

typedef long long int64;
const int64 INF = 1LL << 58;
typedef pair< int64, pair< int, int > > Pi;

struct edge
{
  int vv, time, cost, nxt_ptr;

  bool operator<(const edge &e) const
  {
    return (time < e.time);
  }

  bool operator<(int t) const
  {
    return (time < t);
  }
};

int main()
{
  int N, M, S, G;
  vector< edge > g[100000];

  cin >> N >> M >> S >> G;
  --S, --G;

  for(int i = 0; i < M; i++) {
    int u, v, t, c;
    cin >> u >> v >> t >> c;
    --u, --v;
    g[u].push_back((edge) {v, t, c});
  }

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

  for(int i = 0; i < N; i++) {
    for(auto &e : g[i]) {
      e.nxt_ptr = lower_bound(begin(g[e.vv]), end(g[e.vv]), e.time + e.cost) - begin(g[e.vv]);
    }
  }


  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  map< pair< int, int >, int64 > vv;
  que.emplace(g[S][0].time, make_pair(S, 0));
  vv[{S, 0}] = g[S][0].time;

  while(!que.empty()) {
    auto p = que.top();
    que.pop();

    int idx, now;
    tie(idx, now) = p.second;

    if(p.first > vv[{idx, now}]) continue;

    if(idx == G) {
      cout << p.first << endl;
      return (0);
    }

    if(now + 1 < g[idx].size()) {
      int64 nt = p.first + g[idx][now + 1].time - g[idx][now].time;
      if(!vv.count({idx, now + 1}) || nt < vv[{idx, now + 1}]) {
        vv[{idx, now + 1}] = nt;
        que.emplace(nt, make_pair(idx, now + 1));
      }
    }

    if(now < g[idx].size()) {
      auto &ee = g[idx][now];
      int64 nt = p.first;
      if(ee.vv != G) {
        if(ee.nxt_ptr >= g[ee.vv].size()) continue;
        nt += g[ee.vv][ee.nxt_ptr].time - (ee.time + ee.cost);
      }
      if(!vv.count({ee.vv, ee.nxt_ptr}) || nt < vv[{ee.vv, ee.nxt_ptr}]) {
        vv[{ee.vv, ee.nxt_ptr}] = nt;
        que.emplace(nt, make_pair(ee.vv, ee.nxt_ptr));
      }
    }
  }

}