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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define HUGE_NUM 9999999999999999

struct Info{
	Info(int arg_to,ll arg_time,ll arg_cost,ll arg_min_rain){
		to = arg_to;
		time = arg_time;
		cost = arg_cost;
		min_rain = arg_min_rain;
	}
	int to;
	ll time,cost,min_rain;
};

struct Data{
	Data(int arg_node_id,int arg_pre_node,int arg_pre_id,ll arg_current_time,ll arg_rain_time){
		node_id = arg_node_id;
		pre_node = arg_pre_node;
		pre_id = arg_pre_id;
		current_time = arg_current_time;
		rain_time = arg_rain_time;
	}
	bool operator<(const struct Data &arg) const{
		return rain_time > arg.rain_time;
	}
	int node_id,pre_node,pre_id;
	ll current_time,rain_time;
};

int N,M,start,goal;
vector<Info> G[100000];

int main(){

	scanf("%d %d %d %d",&N,&M,&start,&goal);
	start--;
	goal--;

	int from,to;
	ll time,cost;

	for(int loop = 0; loop < M; loop++){
		scanf("%d %d %lld %lld",&from,&to,&time,&cost);
		from--;
		to--;
		G[from].push_back(Info(to,time,cost,HUGE_NUM));
	}

	priority_queue<Data> Q;
	for(int i = 0; i < G[start].size(); i++){
		G[start][i].min_rain = G[start][i].time;
		Q.push(Data(G[start][i].to,start,i,G[start][i].time+G[start][i].cost,G[start][i].time));
	}

	while(!Q.empty()){

		if(Q.top().node_id == goal){
			printf("%lld\n",Q.top().rain_time);
			return 0;
		}else if(Q.top().rain_time > G[Q.top().pre_node][Q.top().pre_id].min_rain){
			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){
				if(Q.top().current_time > G[Q.top().node_id][i].time)continue;
				if(Q.top().rain_time+G[Q.top().node_id][i].time-Q.top().current_time >= G[Q.top().node_id][i].min_rain)continue;

				G[Q.top().node_id][i].min_rain = Q.top().rain_time+G[Q.top().node_id][i].time-Q.top().current_time;
				Q.push(Data(G[Q.top().node_id][i].to,Q.top().node_id,i,G[Q.top().node_id][i].time+G[Q.top().node_id][i].cost,G[Q.top().node_id][i].min_rain));
			}
			Q.pop();
		}
	}

	return 0;
}