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 ll;
const ll MOD = 1e9 + 7;
using PII = pair<ll, ll>;
#define FOR(i,a,n) for(ll i=(ll)a; i<(ll)n; ++i)
#define REP(i,n) FOR(i,0,n)

struct Edge {
	int to, sttime, cost, index;
	Edge(const int t, const int s, const int c, const int i) {
		to = t, sttime = s, cost = c, index = i;
		return;
	}
	bool operator<(const Edge&e)const {
		return sttime < e.sttime;
	}
};

int main() {
	int N, M, S, G;
	cin >> N >> M >> S >> G;
	S--, G--;
	vector<vector<Edge>>edge(N);
	for (int i = 0; i < M; i++) {
		int l, r, s, t;
		cin >> l >> r >> s >> t;
		l--, r--;
		edge[l].push_back(Edge(r, s, t, i));
	}
//cout << "JHIJHI" << endl;
	for (int i = 0; i < N; i++)sort(edge[i].begin(), edge[i].end());
	vector<vector<pair<int, int>>>dis_edge(M + 1);
//	cout << "GUUG" << endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < (int)(edge[i].size()) - 1; j++) {
			dis_edge[edge[i][j].index].push_back({ edge[i][j + 1].index,edge[i][j + 1].sttime - edge[i][j].sttime });
		}
		vector<pair<int, int>>box;
		for (auto j : edge[i]) {
			if (j.to == G) {
				dis_edge[j.index].push_back({ M,0 });
				continue;
			}
			if (edge[j.to].empty())continue;
			int L = -1, R = edge[j.to].size();
			while (R - L > 1) {
				int mid = (R + L) / 2;
				if (edge[j.to][mid].sttime >= j.sttime + j.cost)R = mid;
				else L = mid;
			}
			if (R == edge[j.to].size())continue;
			dis_edge[j.index].push_back({ edge[j.to][R].index,edge[j.to][R].sttime - j.cost - j.sttime });
		}
	}
	//cout << "Ho" << endl;
	vector<int>dis(M+1, MOD);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>PQ;
	for (auto i : edge[S]) {
		dis[i.index] = i.sttime;
		PQ.push({ i.sttime,i.index });
	}
	while (!PQ.empty()) {
		int cn = PQ.top().second;
		int c = PQ.top().first;
		PQ.pop();
		for (auto j : dis_edge[cn]) {
			if (dis[j.first] > c + j.second) {
				dis[j.first] = c + j.second;
				PQ.push({ dis[j.first],j.first });
			}
		}
	}
	cout << dis[M] << endl;
}