Background

The original version of this problem has relatively weak testdata. If you want to test with stronger testdata, you can go to P6302. Except for the Constraints, everything is the same as the original problem.

Problem Description

In the railway system of Cat Kingdom, there are $n$ stations numbered from $1$ to $n$. A kitten plans to start from station $1$ and take trains to return to its home at station $n$. It has checked the available trains: there are $m$ trains in total, numbered from $1$ to $m$. The kitten will arrive at station $1$ at time $0$.

For train $i$, it departs from station $x_i$ at time $p_i$ and goes directly to station $y_i$, arriving at time $q_i$. The kitten can only board train $i$ at time $p_i$, and can only get off train $i$ at time $q_i$. The kitten can reach station $n$ by transferring multiple times.

A transfer means the following: for two trains, say train $u$ and train $v$, if $y_u = x_v$ and $q_u \leq p_v$, then after taking train $u$, the kitten can wait at station $y_u$ for $p_v - q_u$ time units, and then take train $v$ at time $p_v$.

The kitten wants to get home while reducing the trouble on the way, and it measures this by an “irritation value”.

• While the kitten is waiting at a station, the irritation value increases. For a wait of $t (t \geq 0)$ time units, the irritation value increases by $At^2 + Bt + C$, where $A, B, C$ are given constants. Note: the time it stays at station $1$ starting from time $0$ before boarding the first train also counts as one wait.

• If the kitten finally arrives at station $n$ at time $z$, the irritation value increases by an additional $z$.

Formally, suppose the kitten takes $k$ trains in total, and the sequence of train indices is $s_1, s_2, \cdots , s_k$. This plan is called a feasible route home if and only if it satisfies:

1. $x_{s1} = 1$ , $y_{sk} = n$

2. For all $j (1 \leq j < k)$, $y_{sj} = x_{s_{j+1}}$ and $q_{sj}\leq p_{s_{j+1}}$

For this route home, the irritation value is:

$$q_{s_k}+(A\times p_{s_1}^2+B\times p_{s_1}+C)+\sum_{j=1}^{k-1}(A(p_{s_{j+1}}-q_{s_j})^2+B(p_{s_{j+1}}-q_{s_j})+C)$$

The kitten wants the irritation value to be as small as possible. Please compute, among all feasible routes home, the minimum possible irritation value. The problem guarantees that at least one feasible route exists.

Input Format

The first line contains five integers $n, m, A, B, C$. Their meanings are as described in the statement.

The next $m$ lines: line $i$ contains four integers $x_i, y_i, p_i, q_i$, representing the departure station, arrival station, departure time, and arrival time of train $i$.

Output Format

Output one integer in a single line, the required answer.

3 4 1 5 10
1 2 3 4
1 2 5 7
1 2 6 8
2 3 9 10

94

4 3 1 2 3
1 2 2 3
2 3 5 7
3 4 7 9

34

Hint

More Samples

You can obtain more samples through the additional files.

Sample 3

See route/route3.in and route/route3.ans in the additional files.

The data type of this sample is the same as that of final test points $5 \sim 8$.

Sample 4

See route/route4.in and route/route4.ans in the additional files.

The data type of this sample is the same as that of final test points $11 \sim 14$.

Sample 5

See route/route5.in and route/route5.ans in the additional files.

The data type of this sample is the same as that of final test points $18 \sim 20$.

Explanation for Sample 1

There are three feasible routes home:

• Take trains 1 and 4 in order. The irritation value is: $10 + (1 \times 3^2 + 5 \times 3 + 10) + (1 \times (9 - 4)^2 + 5 \times (9 - 4) + 10)= 104$
• Take trains 2 and 4 in order. The irritation value is: $10 + (1 \times 5^2 + 5 \times 5 + 10) + (1 \times (9 - 7)^2 + 5 \times (9 - 7) + 10)= 94$
• Take trains 3 and 4 in order. The irritation value is: $10 + (1 \times 6^2 + 5 \times 6 + 10) + (1 \times (9 - 8)^2 + 5 \times (9 - 8) + 10)= 102$

The second route has the smallest irritation value, which is $94$.

Constraints

For all test points: $2\le n\le 10^5,1\le m\le 2\times 10^5,0 \le A \le 10 , 0 \le B, C \le 10^6,1 \le x_i, y_i \le n , x_i \neq y_i , 0 \le p_i < q_i \le 10^3$.

The specific limits for each test point are shown in the table below:

::cute-table{tuack}

Test Point ID	$n$	$m$	Special Limits on $A,B,C$	Other Special Conditions
$1\sim 2$	$\le 100$	$=n-1$	None	$y_i=x_i+1$
$3\sim 4$	^	$\le 100$	$A=B=C=0$	^
$5\sim 8$	$\le 2\times 10^3$	$\le 4\times 10^3$	^	$x_i<y_i$
$9$	^		$A=B=0$	^
$10$			$A=0$
$11\sim 14$			None
$15$	$\le 10^5$	$\le 2\times 10^5$	$A=B=0$	^
$16\sim 17$	^		$A=0$
$18\sim 20$			None

Translated by ChatGPT 5