8009 - 回家路线

猫国的铁路系统中有 nn 个站点，从 1−n1−n 编号。小猫准备从 11 号站点出发，乘坐列车回到猫窝所在的 nn 号站点。它查询了能够乘坐的列车，这些列车共 mm 班，从 1−m1−m 编号。小猫将在 00 时刻到达 11 号站点。对于 ii 号列车，它将在时刻 pip_i 从站点 xix_i 出发，在时刻 qiq_i 直达站点 yiy_i ，小猫只能在时刻 pip_i 上 ii 号列车，也只能在时刻 qiq_i 下 ii 号列车。小猫可以通过多次换乘到达 nn 号站点。一次换乘是指对于两班列车，假设分别为 uu 号与 vv 号列车，若 yu=xvy_u=x_v 并且 qu≤pvq_u≤p_v ，那么小猫可以乘坐完 uu 号列车后在 yuy_u 号站点等待 pv−qup_v − q_u 个时刻，并在时刻 pvp_v 乘坐 vv 号列车。

小猫只想回到猫窝并且减少途中的麻烦，对此它用烦躁值来衡量。

  • 小猫在站点等待时将增加烦躁值，对于一次 t(t≥0)t(t≥0) 个时刻的等待，烦躁值将增加 At2+Bt+CAt^2+Bt+C，其中 A,B,CA,B,C 是给定的常数。注意：小猫登上第一班列车前，即从 00 时刻起停留在 11 号站点的那些时刻也算作一次等待。
  • 若小猫最终在时刻 zz 到达 nn 号站点，则烦躁值将再增加 zz。

形式化地说，若小猫共乘坐了 k 班列车，依次乘坐的列车编号可用序列 s1,s2,...,sks_1,s_2,...,s_k 表示。该方案被称作一条可行的回家路线，当且仅当它满足下列两个条件：

对于该回家路线，小猫得到的烦躁值将为：

小猫想让自己的烦躁值尽量小，请你帮它求出所有可行的回家路线中，能得到的最 小的烦躁值。题目保证至少存在一条可行的回家路线。

输入

第一行五个整数 n,m,A,B,Cn,m,A,B,C，变量意义见题目描述。

接下来 mm 行，第 ii 行四个整数 xi,yi,pi,qix_i,y_i,p_i,q_i，分别表示 i 号列车的出发站、到达站、出发时刻与到达时刻。

对于所有测试点：2≤n≤105,1≤m≤2×105,0≤A≤10,0≤B,C≤1062≤n≤ 10^5 ,1≤m≤2× 10^5 ,0≤A≤10,0≤B,C≤10^6
1≤xi,yi≤n,xi≠yi,0≤pi<qi≤1031≤x_i,y_i≤n,x_i≠y_i,0≤p_i < q_i≤10^3

输出

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

样例

输入
复制

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

提示

*本题测试数据为模拟数据，和赛场测试数据不同，本题测试数据难度较低，可以不用斜率优化

对于样例1 共有三条可行的回家路线：

依次乘坐 1，4 号列车，得到的烦躁值为：10+(1×32+5×3+10)+(1×(9−4)2+5×(9−4)+10)=10410+(1×3^2+5×3+10)+(1×(9−4)^2+5×(9−4)+10)=104
依次乘坐 2，4 号列车，得到的烦躁值为：10+(1×52+5×5+10)+(1×(9−7)2+5×(9−7)+10)=9410+(1×5^2+5×5+10)+(1×(9−7)^2+5×(9−7)+10)=94
依次乘坐 3，4 号列车，得到的烦躁值为：10+(1×62+5×6+10)+(1×(9−8)2+5×(9−8)+10)=10210+(1×6^2+5×6+10)+(1×(9−8)^2+5×(9−8)+10)=102
第二条路线得到的烦躁值最小为 94。

来源

NOI

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题