### 问题描述

未来国有 $N$ 个村庄，由 $1 \sim N$ 标号，这些村庄之间有 $M$ 条双向通路，每条道路都有两个属性：维修工期 $g$ 和耐久度 $s$ 。两个村庄之间可能有多条道路，并且可能存在某一村庄与自身连接起来的道路。后来由于战争的原因，这些道路全部被毁掉了。未来国的人民不得不想办法重新修建道路，保证任意两个村庄相互可达。

修建一条道路的花费是： $P \times max\{所有修建道路的属性g\}+Q \times max\{所有修建道路的属性s\}$，其中 $P$ 和 $Q$ 是给定的值。未来国的施工队想要在满足连通性的前提下花费最小，现在请你算出这个花费。

输入格式

第一行包含两个正整数 $N$ 和 $M$ 。

第二行包含两个正整数 $P$ 和 $Q$ 。

后面的 $M$ 行每行描述一条道路，包含四个正整数 $u,v,g,s$ ，分别表示道路连接的两个城市以及道路的两个属性。

输出格式

输出一个整数，表示最小花费。

如果无论如何不能满足连通性，输出 $-1$ 。

样例输入

3 3
2 1
1 2 10 15
1 2 4 20
1 3 5 1

样例输出

30

数据范围

对于 $10\%$ 的数据，$1 \le N \le 10,1 \le M \le 20$。$1 \le P,Q,g,s \le 1000$。

对于 $30\%$ 的数据，$1 \le N \le 100,1 \le M \le 1000$。$1 \le P,Q,g,s \le 1000$。

对于 $50\%$ 的数据，$1 \le N \le 200,1 \le M \le 5000$。$1 \le P,Q,g,s \le 10^9$。

对于 $100\%$ 的数据，$1 \le N \le 400,1 \le M \le 50000$。$1 \le P,Q,g,s \le 10^9$。