Hide

Problem D
Avoiding Airports

/problems/avoidingairports/file/statement/en/img-0001.png
David is looking to book some travel over the world. There are $n$ countries that he can visit, and $m$ flights that are available. The $i$th flight goes from country $a_ i$ to country $b_ i$. It departs at time $s_ i$, and lands at time $e_ i$.

David is currently at the airport in country $1$, and the current time is $0$, and he would like to travel country $n$. He does not care about the total amount of time needed to travel, but he really hates waiting in the airport. If he waits $t$ seconds in an airport, he gains $t^2$ units of frustration. Help him find an itinerary that minimizes the sum of frustration.

Input

The first line of input contains two space-separated integers $n$ and $m$ ($1 \le n,m \le 200\, 000$).

Each of the next $m$ lines contains four space-separated integers $a_ i$, $b_ i$, $s_ i$, and $e_ i$ ($1 \le a_ i, b_ i \le n$; $0 \le s_ i \le e_ i \le 10^6$).

A flight might have the same departure and arrival country.

No two flights will have the same arrival time, or have the same departure time. In addition, no flight will have the same arrival time as the departure time of another flight. Finally, it is guaranteed that there will always be a way for David to arrive at his destination.

Output

Print, on a single line, the minimum sum of frustration.

Examples

In the first sample, it is optimal to take this sequence of flights:

  • Flight $5$. Goes from airport $1$ to airport $2$, departing at time $3$, arriving at time $8$.

  • Flight $3$. Goes from airport $2$ to airport $1$, departing at time $9$, arriving at time $12$.

  • Flight $7$. Goes from airport $1$ to airport $3$, departing at time $13$, arriving at time $27$.

  • Flight $8$. Goes from airport $3$ to airport $5$, deparing at time $28$, arriving at time $100$.

The frustration for each flight is $3^2, 1^2, 1^2,$ and $1^2$, respectively. Thus, the total frustration is $12$.

Note that there is an itinerary that gets David to his destination faster. However, that itinerary has a higher total frustration.

Sample Input 1 Sample Output 1
5 8
1 2 1 10
2 4 11 16
2 1 9 12
3 5 28 100
1 2 3 8
4 3 20 21
1 3 13 27
3 5 23 24
12
Sample Input 2 Sample Output 2
3 5
1 1 10 20
1 2 30 40
1 2 50 60
1 2 70 80
2 3 90 95
1900

Please log in to submit a solution to this problem

Log in