ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Regional School Programming Contest 2019

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. City Building

Time limit: 3.0 second
Memory limit: 256 MB
After a difficult contest, nothing helps Valya relax like playing a city building simulator. The goal of the simulator is to build a perfect city, a real utopia for its many residents. Unfortunately, Valya isn’t always successful: he always ends up lacking either resources or patience.
Today Valya started from scratch. He now has a village with n people, who live alone in their houses. They are numbered from 1 to n. Villagers immidiately declared their needs: they want to be able to visit each other, and for that some roads need to be laid down. In total there are m requests, i-th request comes from villager ai, who wants to be able to visit villager bi.
At this point of the game only two types of roads are available: one-way and two-way. An one-way road costs x dollars, and a two-way road costs y dollars. Each road connects two houses. There are no limits to building roads, and multiple roads between the same pair of houses are allowed. At the start there are no roads.
A villager can visit another villager if there exists a path connecting their houses. A path may consist of multiple roads. Note that two-way roads can be traversed both ways, while an one-way road can only be walked from start to end and not backwards.
What’s the minimal amount of money enough to build roads that satisfy all requests? It’s not necessary to provide villagers a path back to their houses.

Input

The first line contains four integers separated with spaces: n, m, x and y — number of villagers, number of requests, the cost of an one-way road and the cost of a two-way road (2 ≤ n ≤ 105, 1 ≤ m ≤ 105, 1 ≤ x, y ≤ 109).
Each of next m lines contain two space-separated integers each: ai and bi, denoting that villager ai wants to be able to visit villager bi (1 ≤ ai, bin, aibi). It is guaranteed that all requests are different: if ij then aiaj or bibj.

Output

Ouput one number — the minimal amount of money enough to satisfy all requests.

Samples

inputoutput
4 3 2 3
1 2
1 3
2 3
4
4 3 2 3
1 2
1 3
2 1
5
4 4 2 3
1 2
2 1
1 3
3 1
6
Problem Author: Valentine Zuev
To submit the solution for this problem go to the Problem set: 2147. City Building