Problem Background

The original problem has weaker data. If you want to test stronger data, you can visit P6302, which is identical to the original problem except for the data range.

Problem Description

In the railway system of Cat Country, there are $n$ stations numbered from $1$ to $n$. A cat plans to travel from station $1$ to its home at station $n$ by train. It has checked the available trains, which total $m$ in number, numbered from $1$ to $m$. The cat will arrive at station $1$ at time $0$. For the $i$-th train, it departs from station $x_i$ at time $p_i$ and arrives directly at station $y_i$ at time $q_i$. The cat can only board the $i$-th train at time $p_i$ and disembark at time $q_i$. The cat can reach station $n$ through multiple transfers. A transfer involves two trains, say $u$ and $v$, where $y_u = x_v$ and $q_u \leq p_v$. The cat can then wait at station $y_u$ for $p_v - q_u$ moments and board train $v$ at time $p_v$.

The cat wants to minimize its discomfort during the journey, measured by a frustration value.

• The cat's frustration increases while waiting at a station. For a wait of $t$ (where $t \geq 0$) moments, the frustration increases by $At^2 + Bt + C$, where $A, B, C$ are given constants. Note: The wait from time $0$ at station $1$ before boarding the first train is also considered a wait.

• If the cat arrives at station $n$ at time $z$, the frustration increases by $z$.

Formally, if the cat takes $k$ trains in sequence, denoted by the sequence $s_1, s_2, \cdots, s_k$, this route is considered a feasible homeward journey if it satisfies:

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

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

The frustration value for this journey 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 cat wants to minimize its frustration. Help it find the minimum frustration value among all feasible homeward routes. The problem guarantees at least one feasible homeward route exists.

Input Format

The first line contains five integers $n, m, A, B, C$, with meanings as described in the problem.

The next $m$ lines, each containing four integers $x_i, y_i, p_i, q_i$, represent the departure station, arrival station, departure time, and arrival time of the $i$-th train, respectively.

Output Format

Output a single integer, the minimum frustration value.

Sample Input and Output

Sample Input #1

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

Sample Output #1

94

Sample Input #2

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

Sample Output #2

34

Notes/Hints

More Samples

You can obtain more samples through the attached files.

Sample 3

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

This sample matches the data type of final test points $5 \sim 8$.

Sample 4

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

This sample matches the data type of final test points $11 \sim 14$.

Sample 5

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

This sample matches the data type of final test points $18 \sim 20$.

Sample 1 Explanation

There are three feasible homeward routes:

• Taking trains 1 and 4 in sequence, the frustration value is: $10 + (1 \times 3^2 + 5 \times 3 + 10) + (1 \times (9 - 4)^2 + 5 \times (9 - 4) + 10) = 104$
• Taking trains 2 and 4 in sequence, the frustration value is: $10 + (1 \times 5^2 + 5 \times 5 + 10) + (1 \times (9 - 7)^2 + 5 \times (9 - 7) + 10) = 94$
• Taking trains 3 and 4 in sequence, the frustration 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 yields the minimum frustration value of $94$.

Data Range

For all test cases: $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$.

Specific constraints for each test point are detailed in the table below:

见题面 Input 部分

见题面 Output 部分