奥林匹亚王国由N个城市和M条双向道路组成。每条道路恰好连接两个城市,两个城市可以用多条道路连接。也有可能一些道路将城市与城市本身连接起来,形成一个环路。
所有道路都不断遭到强盗的掠夺。过了一段时间,强盗们厌倦了在道路抢劫中浪费时间,所以他们建议奥林匹亚国王还钱。根据报价,土匪想要得到一份由金币和银币组成的礼物。优惠还包含一系列限制:对于每条道路,已知 gi(金币的最小数量)和 si(阻止路上抢劫的礼物中应包含的最小银币数量)。即如果礼物中含有a金币和b银币,那么土匪就会在所有gi≤a且si≤b的道路上停止抢劫。
不幸的是,王国国库既没有金币也没有银币,但里面有奥林匹斯图格里克。一枚图格里克金币的成本是 G,一枚图格里克银币的成本是 S。国王确实想送给强盗这样的礼物,即对于任何两个城市来说,它们之间都存在一条安全路径。你的任务是找到所需礼物的最低奥林匹亚图格里克成本。
输入
输入的第一行包含两个整数 N 和 M (2 ≤ N ≤ 200, 1 ≤ M ≤ 50 000) — 分别是城市数量和道路数量。第二行包含两个整数 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$$。
示例
输入 #1
3 3 2 1 1 2 10 15 1 2 4 20 1 3 5 1
输出 #1
30