题目描述

给出一个带权无向图，边的权值是关于权值成线性关系的。

第 $i$ 条边 $t$ 时刻的权值为 $a_i\times t+b_i$。

求出在时间段 $[t_1,t_2]$ 内使最小生成树权和最大的时刻和此时的权和。

输入格式

第一行四个正整数 $n,m,t_1,t_2$，$n$ 和 $m$ 分别为点数和边数，点从 $0$ 到 $n-1$ 编号。

下面 $m$ 行每行四个整数 $u,v,a,b$，分别描述每条边连接的端点编号和边权关于时间的变化关系。

输出格式

一行两个浮点数，分别表示使最小生成树权和最大的时刻的此时的权和，保留三位小数。

5 6 0 5
1 0-6 -4
2 0 3 -3
3 0 1 5
3 1 -2 -3
4 1-3 -2
4 3 -2 -3

0.000 -13.000

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 200$，$1\leq m\leq 1.2\times 10^3$。