[NOI2019] 回家路线

本题原题数据强度较低，若想要测试较强数据可以去 [P6302](https://www.luogu.com.cn/problem/P6302)，除数据范围外均与原题相同。

猫国的铁路系统中有 $n$ 个站点，从 $1 - n$ 编号。小猫准备从 $1$ 号站点出发，乘坐列车回到猫窝所在的 $n$ 号站点。它查询了能够乘坐的列车，这些列车共 $m$ 班，从$1 - m$编号。小猫将在 $0$ 时刻到达 $1$ 号站点。对于 $i$ 号列车，它将在时刻 $p_i$ 从站点 $x_i$ 出发，在时刻 $q_i$ 直达站点 $y_i$，小猫只能在时刻 $p_i$ 上 $i$ 号列车，也只能在时刻 $q_i$ 下 $i$ 号列车。小猫可以通过多次换乘到达 $n$ 号站点。一次换乘是指对于两班列车，假设分别为 $u$ 号与 $v$ 号列车，若 $y_u = x_v$ 并且 $q_u \leq p_v$，那么小猫可以乘坐完 $u$ 号列车后在 $y_u$ 号站点等待 $p_v - q_u$ 个时刻，并在时刻 $p_v$ 乘坐 $v$ 号列车。 小猫只想回到猫窝并且减少途中的麻烦，对此它用烦躁值来衡量。 - 小猫在站点等待时将增加烦躁值，对于一次 $t (t \geq 0)$ 个时刻的等待，烦躁值将增加 $At^2 + Bt + C$，其中 $A, B,C$ 是给定的常数。注意：小猫登上第一班列车前，即从 $0$ 时刻起停留在 $1$ 号站点的那些时刻也算作一次等待。 - 若小猫最终在时刻 $z$ 到达 $n$ 号站点，则烦躁值将再增加 $z$。 形式化地说，若小猫共乘坐了 $k$ 班列车，依次乘坐的列车编号可用序列 $s_1, s_2, \cdots , s_k$表示。该方案被称作一条可行的回家路线，当且仅当它满足下列两个条件： 1. $x_{s1} = 1$ , $y_{sk} = n$ 2. 对于所有 $j (1 \leq j < k)$，满足 $y_{sj} = x_{s_{j+1}}$ 且 $q_{sj}\leq p_{s_{j+1}}$ 对于该回家路线，小猫得到的烦躁值将为： $$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)$$ 小猫想让自己的烦躁值尽量小，请你帮它求出所有可行的回家路线中，能得到的最 小的烦躁值。题目保证至少存在一条可行的回家路线。

第一行五个整数 $n, m, A, B,C$，变量意义见题目描述。 接下来 $m$ 行，第 $i$ 行四个整数 $x_i, y_i, p_i, q_i$，分别表示 $i$ 号列车的出发站、到达站、出发时刻与到达时刻。

输出仅一行一个整数，表示所求的答案。

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

### 更多样例 您可以通过附加文件获得更多样例。 #### 样例 3 见附加文件的 `route/route3.in` 与 `route/route3.ans`。 该样例的数据类型与最终测试点 $5 \sim 8$ 一致。 #### 样例 4 见附加文件的 `route/route4.in` 与 `route/route4.ans`。 该样例的数据类型与最终测试点 $11 \sim 14$ 一致。 #### 样例 5 见附加文件的 `route/route5.in` 与 `route/route5.ans`。 该样例的数据类型与最终测试点 $18 \sim 20$ 一致。 ### 样例 1 解释 共有三条可行的回家路线： - 依次乘坐 1，4 号列车，得到的烦躁值为：$10 + (1 \times 3^2 + 5 \times 3 + 10) + (1 \times (9 - 4)^2 + 5 \times (9 - 4) + 10)= 104$ - 依次乘坐 2，4 号列车，得到的烦躁值为：$10 + (1 \times 5^2 + 5 \times 5 + 10) + (1 \times (9 - 7)^2 + 5 \times (9 - 7) + 10)= 94$ - 依次乘坐 3，4 号列车，得到的烦躁值为：$10 + (1 \times 6^2 + 5 \times 6 + 10) + (1 \times (9 - 8)^2 + 5 \times (9 - 8) + 10)= 102$ 第二条路线得到的烦躁值最小为 $94$。 ### 数据范围 对于所有测试点：$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$。 每个测试点的具体限制见下表： | 测试点编号 | $n$ | $m$ | $A,B,C$ 的特殊限制 | 其他特殊条件 | | :---------: | :----------------: | :-------------------: | :----------------: | :----------: | | $1\sim 2$ | $\le 100$ | $=n-1$ | 无 | $y_i=x_i+1$ | | $3\sim 4$ | $\le 100$ | $\le 100$ | $A=B=C=0$ | $y_i=x_i+1$ | | $5\sim 8$ | $\le 2\times 10^3$ | $\le 4\times 10^3$ | $A=B=C=0$ | $x_i<y_i$ | | $9$ | $\le 2\times 10^3$ | $\le 4\times 10^3$ | $A=B=0$ | $x_i<y_i$ | | $10$ | $\le 2\times 10^3$ | $\le 4\times 10^3$ | $A=0$ | $x_i<y_i$ | | $11\sim 14$ | $\le 2\times 10^3$ | $\le 4\times 10^3$ | 无 | 无 | | $15$ | $\le 10^5$ | $\le 2\times 10^5$ | $A=B=0$ | 无 | | $16\sim 17$ | $\le 10^5$ | $\le 2\times 10^5$ | $A=0$ | 无 | | $18\sim 20$ | $\le 10^5$ | $\le 2\times 10^5$ | 无 | 无 |