Background

This problem is an enhanced version of NOI 2019 Route Home. Except for the Constraints, it is the same as the original problem.

Problem Description

In the railway system of Cat Kingdom, there are $n$ stations, numbered from $1 - n$. The kitten plans to start from station $1$ and take trains to return to station $n$, where its home is. It checked the trains it can take. There are $m$ trains in total, numbered from $1 - 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 arrives directly at station $y_i$ 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: for two trains, suppose they are 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 board train $v$ at time $p_v$.

The kitten only wants to get home and reduce the trouble on the way, so it uses an irritation value to measure this.

• When the kitten waits at a station, its irritation value increases. For one 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 spent staying at station $1$ starting from time $0$ before boarding the first train is also counted as one wait.

• If the kitten finally arrives at station $n$ at time $z$, the irritation value will further increase by $z$.

Formally, suppose the kitten takes $k$ trains in total, and the train numbers it takes in order can be written as a sequence $s_1, s_2, \cdots , s_k$. This plan is called a feasible route home if and only if it satisfies the following two conditions:

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

• 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 the kitten gets 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 help it find the minimum irritation value among all feasible routes home. The problem guarantees that there is at least one feasible route home.

Input Format

The first line contains five integers $n, m, A, B, C$. The meanings of the variables are given in the description.

The next $m$ lines describe the trains. In line $i$, there are four integers $x_i, y_i, p_i, q_i$, representing the departure station, arrival station, departure time, and arrival time of train $i$, respectively.

Output Format

Output only one line with one integer, 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

For all testdata, it is guaranteed that $2\le n\le 10^5$, $1\le m\le 10^6$, $0\le A\le 10$, $0\le B, C\le 10^7$, $1\le x_i, y_i\le n$, $x_i\neq y_i$, and $0\le p_i<q_i\le 4\times 10^4$.

Translated by ChatGPT 5