题目背景
本题是 NOI 2019 回家路线的加强版,除数据范围外均与原题相同。
题目描述
猫国的铁路系统中有 n 个站点,从 1−n 编号。小猫准备从 1 号站点出发,乘坐列车回到猫窝所在的 n 号站点。它查询了能够乘坐的列车,这些列车共 m 班,从 1−m 编号。小猫将在 0 时刻到达 1 号站点。对于 i 号列车,它将在时刻 pi 从站点 xi 出发,在时刻 qi 直达站点 yi,小猫只能在时刻 pi 上 i 号列车,也只能在时刻 qi 下 i 号列车。小猫可以通过多次换乘到达 n 号站点。一次换乘是指对于两班列车,假设分别为 u 号与 v 号列车,若 yu=xv 并且 qu≤pv,那么小猫可以乘坐完 u 号列车后在 yu 号站点等待 pv−qu 个时刻,并在时刻 pv 乘坐 v 号列车。
小猫只想回到猫窝并且减少途中的麻烦,对此它用烦躁值来衡量。
-
小猫在站点等待时将增加烦躁值,对于一次 t(t≥0) 个时刻的等待,烦躁值将增加 At2+Bt+C,其中 A,B,C 是给定的常数。注意:小猫登上第一班列车前,即从 0 时刻起停留在 1 号站点的那些时刻也算作一次等待。
-
若小猫最终在时刻 z 到达 n 号站点,则烦躁值将再增加 z。
形式化地说,若小猫共乘坐了 k 班列车,依次乘坐的列车编号可用序列 s1,s2,⋯,sk 表示。该方案被称作一条可行的回家路线,当且仅当它满足下列两个条件:
-
xs1=1,ysk=n
-
对于所有 j(1≤j<k),满足 ysj=xsj+1 且 qsj≤psj+1
对于该回家路线,小猫得到的烦躁值将为:
qsk+(A×ps12+B×ps1+C)+j=1∑k−1(A(psj+1−qsj)2+B(psj+1−qsj)+C)小猫想让自己的烦躁值尽量小,请你帮它求出所有可行的回家路线中,能得到的最 小的烦躁值。题目保证至少存在一条可行的回家路线。
输入格式
第一行五个整数 n,m,A,B,C,变量意义见题目描述。
接下来 m 行,第 i 行四个整数 xi,yi,pi,qi,分别表示 i 号列车的出发站、到达站、出发时刻与到达时刻。
输出格式
输出仅一行一个整数,表示所求的答案。
提示
对于所有的测试点,保证 2≤n≤105,1≤m≤106,0≤A≤10,0≤B,C≤107,1≤xi,yi≤n,xi=yi,0≤pi<qi≤4×104。