TAP2015D - Happiness for all

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf ]

The separatist state of Nlogonia has N cities numbered 1 through N. Some pairs of cities are connected by highways, so that if there is a highway between city A and city B it is possible to travel from A to B or from B to A. We say that a citizen from city i can visit another from city j if there exists a sequence of different cities c1, c2, ..., cm with m ≥ 2 such that c1 = i, cm = j and there is a highway between cities ck and ck+1 for k = 1, 2, ..., m-1.

The people of Nlogonia are very sociable, so they have friends in all the cities they can visit. However, they are also a bit lazy, so that they are not happy unless they can visit each of their friends by taking exactly one highway directly from their city to their friend's.

To avoid Nlogonia's scission, the queen has decided to perform a number of infrastructure works in order to make all of its citizens happy. One possibility consists in building new highways between the cities of Nlogonia, incurring in a cost of R per new highway built. Because building many highways can be very expensive, another possibility is to build stadiums in some of Nlogonia's cities. The building of a stadium costs E, and immediately makes all the citizens happy in the city where it is built. Then again, you should know that Nlogonia's inhabitants are furthermore somewhat jealous, so that they shall never be happy if there is no stadium in their own city, but there is one in some of their friend's cities. Can you help the queen calculate the minimum cost of the construction work necessary to make everyone in Nlogonia happy?

 

Input

There are multiple test cases in the input file. For each test case, the first line contains four integers N, M, R and E. The number N represents the number of cities in Nlogonia (2 ≤ N ≤ 1000), M represents the original number of highways (1 ≤ M ≤ 105), whereas R and E represent the cost of building a highway and a stadium, respectively (1 ≤ R, E ≤ 1000). Each of the following M lines describes a different highway using two integers A and B, representing the cities connected by said highway (1 ≤ A, B ≤ N with A ≠ B).

 

Output

For each test case, print one line containing an integer representing the minimum cost of the construction work necessary to make everyone in Nlogonia happy.

 

Example

Input:
9 6 11 12
1 2
3 2
4 5
5 6
6 7
9 7

Output:
71 

hide comments
avisheksanvas: 2016-07-12 13:54:57

Dfs with some logic ;)
And don't forget EOF!

Daksh: 2015-12-23 19:06:31

dfs :)

Oasis: 2015-11-06 09:01:27

Easy One..Take care that there are multiple test cases...costed me 1 WA


Added by:Fidel Schaposnik
Date:2015-10-28
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Argentinian Programming Tournament 2015