### 问题描述 未来国有 $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$ 。 ### 样例输入 ```plaintext 3 3 2 1 1 2 10 15 1 2 4 20 1 3 5 1 ``` ### 样例输出 ```plaintext 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$。