时间限制： 1.0 秒 3.0 秒

空间限制： 512 MB

题目描述

Bob 要去 CACC 国旅行了，CACC 国有 $n$ 个城市，以及 $m$ 段单向运行的铁路，Bob 将从 $1$ 号城市出发，并以 $n$ 号城市为终点，完成这次旅行。

CACC国有 $c$ 个铁路公司，每段铁路都属于一个铁路公司，每个铁路公司只运营一条连续的铁路，这条铁路可以分成一些连续的段。

为促进旅游业发展，CACC 国提供了这样的政策：乘坐火车可获得里程点数，里程点数可以累积，用来换取 CACC 国特产礼品。由于里程点数是由铁路公司记录的，所以里程点数的记录规则也和经过铁路所属的铁路公司相关。

具体地，连续地乘坐同一家铁路公司的铁路的长度为 $l$，则本次旅途将提供 $\max(A\times (l-B)^2+C,0)$ 的里程点数，其中 $A,B,C$ 为给定的非负常数。

注意，获得里程点数的条件为连续地乘坐同一家铁路公司的铁路，即如果先乘坐公司 $i$ 的铁路，中间一段换乘了其他铁路公司的铁路，即使后面继续乘坐公司 $i$ 的铁路，这两段长度在里程点数中仍然是分开计算的。如果 Bob 连续乘坐了公司 $i$ 的若干段铁路，他既可以选择将它们按照总长度累计点数，也可以选择将它们分成若干连续的段来分别积累。

Bob 不希望旅途过长，所以他希望他乘坐火车的总里程是最少的，当然，对于 CACC 国的特产礼品，Bob 还是很感兴趣的，所以他希望在上面的前提下，获得的总里程点数最大。题目保证能够最终到达 $n$ 号城市。

输入格式

从标准输入读入数据。

第一行输入六个整数 $n,m,c,A,B,C$，含义如题面所示。

接下来 $m$ 行，每行输入四个整数 $u_i,v_i,l_i,c_i$，描述一条铁路的信息，表示该铁路从 $u_i$ 城市通向 $v_i$ 城市，长度为 $l_i$，所属铁路公司为 $c_i$。

输出格式

输出到标准输出。

输出一行由一个空格隔开的两个整数，依次表示最短总里程和最大总里程点数。

5 5 2 1 2 0
1 2 3 2
2 3 4 1
2 4 7 2
3 4 2 1
4 5 5 2

14 26

样例 1 解释

即使可以全程乘坐 $2$ 号公司的铁路到达终点，总长度为 $15$，并非最短的总长度。

所以应当先乘坐 $2$ 号公司的铁路到达 $2$ 号城市，再乘坐 $1$ 号公司的铁路经由 $3$ 号城市到达 $4$ 号城市，再乘坐 $2$ 号公司的铁路到达 $5$ 号城市，获得的里程点数为 $(3-2)^2+(4+2-2)^2+(5-2)^2=26$。

子任务

对于所有的数据，保证：

• $1\leq n\leq 10^6$；
• $1\leq c,m\leq 2\times 10^6$；
• $0\leq A,B,C\leq 1000$；
• $1\leq l_i\leq 1000$；
• 每个铁路公司的铁路可以连接成连续的一个非环路径，但不一定按输入顺序依次连接
• 可能出现不同公司的铁路连接相同的两个城市的情况

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

提示

本题输入量较大，请采用效率较高的读入方式。

由于部分数据规模较大，你可能需要使用高精度整型数：

• 在 C++ 语言中，你可以使用 G++ 的 __int128 和 unsigned __int128 类型。
• 在 Java 语言中，你可以使用 BigInteger 类。
• 在 Python 语言中，默认的 int 类型即可满足精度要求。