H. Traffic light
time limit per test
3 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Nathan, as usual, went to buy energy drinks to participate in a competition in Astana, Kazakhstan. Since the Kazakh people are health-conscious, energy drinks have become a rarity. For this reason, Nathan has to drive to the only energy drink store in the city and then make his way to the competition location. As always, Nathan didn't plan adequately, and upon arriving at the energy drink store, he realized he might not have enough time to return to the competition. Help Nathan find the shortest time he can reach the competition given that he is at the energy drink store.

The city can be described by a set of $$$M$$$ streets and $$$N$$$ intersections. Each street $$$r_i$$$ is defined by two intersections representing the ends of the street and a traffic light. A traffic light allows or prevents a car from passing through the street it controls, depending on whether it is open or closed. Traffic lights have a known cyclical behavior: the traffic light for street $$$r_i$$$ cycles, being open for $$$x_i$$$ minutes and closed for $$$y_i$$$ minutes. Every traffic light starts its cycle open at time $$$0$$$.

The energy drink store is located at intersection 1, while the competition takes place at intersection $$$N$$$. What is the shortest time Nathan can reach the competition if he starts at the energy drink store at time $$$t$$$?

The time spent driving the car is negligible compared to the waiting time at traffic lights. Since Nathan is not so incapable that he would use a route that makes it impossible to reach the competition, it is guaranteed that there is a way to reach intersection $$$N$$$ starting from intersection $$$1$$$.

Input

The first line of input contains three integers $$$N$$$, $$$M$$$, and $$$t$$$ ($$$2 \le N \le 10^5, N-1 \le M \le 2 \times 10^5, 1 \le t \le 10^9$$$), representing the number of intersections, the number of streets, and the time at which Nathan will leave the energy drink store, respectively.

Each of the next $$$M$$$ lines of input contains four integers $$$a_i$$$, $$$b_i$$$, $$$x_i$$$, $$$y_i$$$ ($$$1 \le a_i,b_i \le N, a_i \ne b_i, 1 \le x_i,y_i \le 10^9$$$), indicating that street $$$r_i$$$ connects intersections $$$a_i$$$ and $$$b_i$$$ and contains a traffic light that cycles, being open for $$$x_i$$$ minutes and closed for $$$y_i$$$ minutes.

It is guaranteed that there is a path from intersection $$$1$$$ to intersection $$$N$$$. No two streets connect the same pair of intersections.

Output

Print a single integer — the shortest time in which Nathan can reach intersection $$$N$$$.

Examples
Input
2 1 3
1 2 4 4
Output
3
Input
2 1 3
1 2 3 4
Output
7
Input
4 4 9
1 2 1 23
2 4 1 10
1 3 1 31
3 4 1 31
Output
32
Input
4 4 9
1 2 1 86
2 4 1 52
1 3 1 60
3 4 1 78
Output
79
Input
3 2 1000000000
3 2 1000000000 1
3 1 1 1000000000
Output
1000000001
Input
3 2 1
3 2 1000000000 1
3 1 1 1000000000
Output
1000000001