#1431. MLand

题目描述

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

第i条边t时刻的权值为Ai*t+Bi.

求出在时间段[t1,t2]内使最小生成树权和最大的时刻和此时的权和

输入格式

第一行四个正整数n,m,t1,t2 n和m分为点数和边数,点从0到n-1编号

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

N<=200,M<=1200

输出格式

只需要输出最小生成树权和的最大值

样例

样例输入

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  

样例输出

-13.000  

数据范围与提示