English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
The output should contain the minimal cost of the gift in Olympian tugriks. If there is no gift that satisfies the given requirements output .
[samples]
奥利匹亚王国由 #cf_span[N] 座城市和 #cf_span[M] 条双向道路组成。每条道路恰好连接两座城市，且两座城市之间可能存在多条道路。此外，某些道路可能连接城市与自身，形成环路。
所有道路持续遭受盗匪劫掠。一段时间后，盗匪厌倦了在道路上浪费时间抢劫，于是向奥利匹亚国王提出和解方案：他们希望收到一份由金币和银币组成的礼物。该方案包含一组限制条件：对于每条道路，已知 #cf_span[gi] 为停止该道路抢劫所需的最少金币数量，#cf_span[si] 为所需的最少银币数量。也就是说，如果礼物包含 #cf_span[a] 枚金币和 #cf_span[b] 枚银币，则所有满足 #cf_span[gi ≤ a] 且 #cf_span[si ≤ b] 的道路都将变得安全。
不幸的是，王国国库中既没有金币也没有银币，只有奥利匹亚图格里克。一枚金币的图格里克价格为 #cf_span[G]，一枚银币的图格里克价格为 #cf_span[S]。国王希望送出一份礼物，使得任意两座城市之间都存在一条安全路径。你的任务是找出满足要求的礼物的最小图格里克成本。
输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[M]（#cf_span[2 ≤ N ≤ 200]，#cf_span[1 ≤ M ≤ 50 000]），分别表示城市数量和道路数量。第二行包含两个整数 #cf_span[G] 和 #cf_span[S]（#cf_span[1 ≤ G, S ≤ 10^9]），分别表示金币和银币的图格里克价格。接下来的 #cf_span[M] 行描述了该方案的每条道路信息，每行包含四个整数 #cf_span[xi, yi, gi, si]，其中 #cf_span[xi] 和 #cf_span[yi] 是该道路连接的两座城市编号，#cf_span[gi] 和 #cf_span[si] 是该道路所需的最少金币和银币数量（#cf_span[1 ≤ xi, yi ≤ N]，#cf_span[1 ≤ gi, si ≤ 10^9]）。城市编号从 #cf_span[1] 到 #cf_span[N]。同一对城市之间可能存在多条道路，也可能存在连接城市与自身的道路。
输出应为满足要求的礼物的最小图格里克成本。如果不存在满足条件的礼物，请输出 .
## Input
输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[M]（#cf_span[2 ≤ N ≤ 200]，#cf_span[1 ≤ M ≤ 50 000]），分别表示城市数量和道路数量。第二行包含两个整数 #cf_span[G] 和 #cf_span[S]（#cf_span[1 ≤ G, S ≤ 10^9]），分别表示金币和银币的图格里克价格。接下来的 #cf_span[M] 行描述了该方案的每条道路信息，每行包含四个整数 #cf_span[xi, yi, gi, si]，其中 #cf_span[xi] 和 #cf_span[yi] 是该道路连接的两座城市编号，#cf_span[gi] 和 #cf_span[si] 是该道路所需的最少金币和银币数量（#cf_span[1 ≤ xi, yi ≤ N]，#cf_span[1 ≤ gi, si ≤ 10^9]）。城市编号从 #cf_span[1] 到 #cf_span[N]。同一对城市之间可能存在多条道路，也可能存在连接城市与自身的道路。
## Output
输出应为满足要求的礼物的最小图格里克成本。如果不存在满足条件的礼物，请输出 .
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of cities, $ M \in \mathbb{Z}^+ $ the number of roads.
Let $ G, S \in \mathbb{Z}^+ $ be the cost in tugriks of one gold and one silver coin, respectively.
Let $ \mathcal{R} = \{ (x_i, y_i, g_i, s_i) \mid i \in \{1, \dots, M\} \} $ be the set of roads, where:
- $ x_i, y_i \in \{1, \dots, N\} $ are the endpoints of road $ i $,
- $ g_i \in \mathbb{Z}^+ $ is the minimum gold coins required to secure road $ i $,
- $ s_i \in \mathbb{Z}^+ $ is the minimum silver coins required to secure road $ i $.
Let $ a \in \mathbb{Z}^+ $ be the number of gold coins in the gift, $ b \in \mathbb{Z}^+ $ the number of silver coins.
A road $ i $ is *secured* if and only if $ a \ge g_i $ and $ b \ge s_i $.
Let $ \mathcal{G}(a,b) $ be the graph on $ N $ vertices containing exactly the secured roads under gift $ (a,b) $.
**Constraints**
1. $ 2 \le N \le 200 $
2. $ 1 \le M \le 50{,}000 $
3. $ 1 \le G, S \le 10^9 $
4. $ 1 \le g_i, s_i \le 10^9 $ for all $ i \in \{1, \dots, M\} $
5. The graph $ \mathcal{G}(a,b) $ must be connected.
**Objective**
Minimize the total cost:
$$
\text{Cost}(a,b) = a \cdot G + b \cdot S
$$
over all pairs $ (a,b) \in \mathbb{Z}^+ \times \mathbb{Z}^+ $ such that $ \mathcal{G}(a,b) $ is connected.
If no such $ (a,b) $ exists, output nothing (or indicate impossibility).
API Response (JSON)
{
"problem": {
"name": "A. Gift",
"description": {
"content": "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 roa",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF76A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 roa...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "奥利匹亚王国由 #cf_span[N] 座城市和 #cf_span[M] 条双向道路组成。每条道路恰好连接两座城市，且两座城市之间可能存在多条道路。此外，某些道路可能连接城市与自身，形成环路。\n\n所有道路持续遭受盗匪劫掠。一段时间后，盗匪厌倦了在道路上浪费时间抢劫，于是向奥利匹亚国王提出和解方案：他们希望收到一份由金币和银币组成的礼物。该方案包含一组限制条件：对于每条道路，已知 #cf_span[...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ N \\in \\mathbb{Z}^+ $ be the number of cities, $ M \\in \\mathbb{Z}^+ $ the number of roads. \nLet $ G, S \\in \\mathbb{Z}^+ $ be the cost in tugriks of one gold and one silver coin...",
"is_translate": false,
"language": "Formal"
}
]
}