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:
/* attention to overflow */
#include <bits/stdc++.h>

#define dump(x) cerr<< #x << " = " << x <<endl
#define ALL(container) (container).begin(),(container).end()

using namespace std;
const int INF = 1 << 25;
void io() { cin.tie(0); ios::sync_with_stdio(false);}
template <class S,class T> ostream& operator<<(ostream& os, const pair <S,T> &s){return os<<'('<<s.first<<','<<s.second<<')';}
/*printf("%.9Lf\n",cf);*/
const int MOD = 1000000007;
const double EPS=1e-8;

int dp[200010];
struct ed{int u,v,t,c;};
vector <ed> eds(200010);
struct edge{int no,u,tc;};
vector <edge> Graph[100010];

int N,M,S,G;

int memo(int q){
	if(dp[q]!=-1) return dp[q];

	int uofq=eds[q].u;
	int tofq=eds[q].t;

	if(uofq==S) return dp[q]=tofq;

	int tmp=INF;
	for(int i=0;i<Graph[uofq].size();i++){
		int no=Graph[uofq][i].no;
		int tc=Graph[uofq][i].tc;
		//if(tc>tofq) continue;
		if(tc>tofq) break;
		tmp=min(tmp,(tofq-tc)+memo(no));
	}
	return dp[q]=tmp;
}

int main() {
	io();
	cin>>N>>M>>S>>G;
	S--,G--;
	fill_n(dp,M+10,-1);
	for(int i=0;i<M;i++){
		int u,v,t,c;
		cin>>u>>v>>t>>c;
		u--,v--;
		Graph[v].push_back({i,u,t+c});

		//eds.push_back({u,v,t,c});
		eds[i]={u,v,t,c};
	}

	for(int i=0;i<N;i++){
		sort(Graph[i].begin(),Graph[i].end(),[](const edge &a, const edge &b){return a.tc<b.tc;});
	}

	int ans=INF;
	for(int i=0;i<M;i++){
		if(eds[i].v==G) ans=min(ans,memo(i));
	}
	cout<<ans<<endl;


	return 0;
}