Gift#2007
The kingdom of Olympia consists of cities and bidirectional roads. Each road connects exactly two cities, and two cities can be connected by more than one road. Also, it is possible that some roads connect a city with itself, forming a loop.
All roads are constantly plundered by bandits. After a while, the bandits became tired of wasting time on road robberies, so they proposed an offer to the king of Olympia. According to their offer, the bandits want to receive a gift consisting of gold and silver coins. The offer also provides 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 that road. That is, if the gift contains gold and silver coins, then the bandits will stop robberies on all the roads where g_i \leq a and s_i \leq b.
Unfortunately, the kingdom's treasury contains neither gold nor silver coins, but there are Olympian tugriks. The cost of one gold coin in tugriks is , and the cost of one silver coin in tugriks is . The king wants to send the bandits such a gift that for every pair of cities, there exists at least one safe path between them.
Your task is to find the minimal cost in Olympian tugriks of the required gift according to the information about the cities, roads, and coin prices.
The first line contains two integers and (2 \leq N \leq 200, 1 \leq M \leq 50\,000) — the number of cities and roads, respectively.
The second line contains two integers and (1 \leq G, S \leq 10^9) — the prices of gold and silver coins in tugriks.
Each of the next lines contains four integers x_i, y_i, g_i, s_i, where x_i and y_i are the numbers of the cities that the -th road connects (1 \leq x_i, y_i \leq N), and g_i, s_i (1 \leq g_i, s_i \leq 10^9) are the minimal gold and silver coins required to stop robberies on the -th road.
Cities are numbered from to . There may be more than one road between a pair of cities. It is possible that a road connects a city with itself.
Print one integer — the minimum number of tugriks the king must spend to buy gold and silver coins to meet the requirements, or if no amount of tugriks can help.
Example 1