题目描述

奥林匹亚王国由N个城市和M条双向道路组成。每条道路正好连接两个城市，两个城市可以连接不止一条道路。也有可能一些道路连接城市与自身形成一个环路。

所有的道路都经常被强盗抢劫。过了一段时间，强盗们厌倦了把时间浪费在公路抢劫上，所以他们建议奥林匹亚国王付钱。根据提议，强盗们想要得到一份由金币和银币组成的礼物。赠礼还包含了一系列限制条件:对于每条道路，赠礼中都有已知的gi(最小数量的金币)和si(最小数量的银币)，以防止道路上的抢劫。也就是说，如果礼物中含有1枚金币和b枚银币，那么强盗将在gi≤a和si≤b的所有道路上停止抢劫。

不幸的是，王国的国库里既没有金币也没有银币，但里面有奥林匹斯的图格里克雕像。一枚金币在图格里克的成本是G，一枚银币在图格里克的成本是s。国王真的想送给强盗这样的礼物，对于任何两个城市来说，他们之间都会存在一条安全的道路。你的任务是用奥林匹斯图格里克语找到所需礼物的最低价格。

输入的第一行包含两个整数N和M(2≤N≤200,1≤M≤50000)，分别是城市数量和道路数量。第二行包含两个整数G和S(1≤G, S≤109)——图格里克金币和银币的价格。下面的M行包含有关报价的信息。列表中的每条记录都以四个整数xi, yi, gi, si给出，其中xi和yi是这条道路连接的城市数量，gi, si是第i条道路所需的最小金币和银币(1≤xi, yi≤N, 1≤gi, si≤109)。城市编号从1到n。一对城市之间可能有不止一条路。有可能有一条路把城市和城市本身连接起来。

输出应该包含礼品在奥林匹斯图格里克的最低成本。如果没有礼品满足给定的输出要求。

【简要题意】 给出一张 $n$ 个点 $m$ 条边的无向连通图, 每条边有两个权 $a_{i}$ 和 $b_{i}$ 。

现在, 你需要确定两个参数 $A, B$ , 使得只保留 $a_{i} \leq A$ 且 $b_{i} \leq B$ 的边后原图仍然联通。

你的目标是最小化 $A \times WA+B \times WB$ , 其中 $WA, WB$ 是输入给 定的常数。 $n \leq 200$ 。

输入格式

输入的第一行包含两个整数N和M(2≤N≤200,1≤M≤50000)，分别是城市数量和道路数量。第二行包含两个整数G和S(1≤G, S≤109)——图格里克金币和银币的价格。下面的M行包含有关报价的信息。列表中的每条记录都以四个整数xi, yi, gi, si给出，其中xi和yi是这条道路连接的城市数量，gi, si是第i条道路所需的最小金币和银币(1≤xi, yi≤N, 1≤gi, si≤109)。城市编号从1到n。一对城市之间可能有不止一条路。有可能有一条路把城市和城市本身连接起来。

输出格式

输出应该包含礼品在奥林匹斯图格里克的最低成本。如果没有满足给定要求的礼物输出-1。

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

30