CF76A.Gift

The kingdom of Olympia consists of N cities and M bidirectional roads. Each road connects exactly two cities and two cities can be connected with more than one road. Also it possible that some roads connect city with itself making a loop.

All roads are constantly plundered with bandits. After a while bandits became bored of wasting time in road robberies, so they suggested the king of Olympia to pay off. According to the offer, bandits want to get a gift consisted of gold and silver coins. Offer also contains a list of restrictions: for each road it is known g__i — the smallest amount of gold and s__i — the smallest amount of silver coins that should be in the gift to stop robberies on the road. That is, if the gift contains a gold and b silver coins, then bandits will stop robberies on all the roads that g__i ≤ a and s__i ≤ b.

Unfortunately kingdom treasury doesn't contain neither gold nor silver coins, but there are Olympian tugriks in it. The cost of one gold coin in tugriks is G, and the cost of one silver coin in tugriks is S. King really wants to send bandits such gift that for any two cities there will exist a safe path between them. Your task is to find the minimal cost in Olympian tugriks of the required gift.

奥林匹亚王国由 $N$ 座城市和 $M$ 条双向道路组成。每条道路恰好连接两座城市，且两座城市之间可能存在多条道路。此外，某些道路也可能连接同一座城市，从而形成自环。

所有道路均持续遭受强盗劫掠。一段时间后，强盗对在道路上实施抢劫感到厌倦，于是向奥林匹亚国王提出“赎买”要求。根据该提议，强盗希望获得一份由金币和银币组成的礼物。该提议还附有一份限制列表：对每条道路 $i$，已知其所需的最少金币数量 $g_i$ 和最少银币数量 $s_i$，即若礼物中包含 $a$ 枚金币和 $b$ 枚银币，则强盗将停止在所有满足 $g_i \leq a$ 且 $s_i \leq b$ 的道路上的劫掠行为。

不幸的是，王国国库中既没有金币也没有银币，仅有奥林匹亚图格里克（tugrik）。一枚金币的价格为 $G$ 图格里克，一枚银币的价格为 $S$ 图格里克。国王迫切希望送给强盗一份礼物，使得任意两座城市之间均存在一条安全路径（即路径上的所有道路均不再被劫掠）。你的任务是求出满足条件的礼物所需的最小总花费（以奥林匹亚图格里克为单位）。

The first line of the input contains two integers N and M (2 ≤ N ≤ 200, 1 ≤ M ≤ 50 000) — the number of cities and the number of roads, respectively. The second line contains two integers G and S (1 ≤ G, S ≤ 109) — the prices of gold and silver coins in tugriks. The following M lines contain information about the offer. Each of the records in list is given as four integers x__i, y__i, g__i, s__i, where x__i and y__i are the numbers of cities that the road connects and g__i, s__i are minimal gold and silver coins requirements for the i-th road (1 ≤ x__i, y__i ≤ N, 1 ≤ g__i, s__i ≤ 109). Cities are numbered from 1 to N. It is possible that there are more than one road between a pair of cities. It is possible that a road connects the city with itself.

输入的第一行包含两个整数 $N$ 和 $M$（$2 \leq N \leq 200$，$1 \leq M \leq 50\,000$），分别表示城市的数量和道路的数量。
第二行包含两个整数 $G$ 和 $S$（$1 \leq G,\,S \leq 10^9$），表示金币与银币在图格里克（tugriks）中的价格。
接下来的 $M$ 行描述了各项通行条件。每条记录由四个整数 $x_i,\,y_i,\,g_i,\,s_i$ 组成，其中 $x_i$ 和 $y_i$ 是该道路所连接的两座城市的编号，$g_i$ 和 $s_i$ 分别是通行第 $i$ 条道路所需的最少金币数与银币数（$1 \leq x_i,\,y_i \leq N$，$1 \leq g_i,\,s_i \leq 10^9$）。城市编号从 $1$ 到 $N$。
同一对城市之间可能存在多条道路；某条道路也可能连接同一座城市（即自环）。

The output should contain the minimal cost of the gift in Olympian tugriks. If there is no gift that satisfies the given requirements output .

输出应为礼物的最小花费（单位：奥林匹亚图格里克）。若不存在满足给定要求的礼物，则输出 。