TAP2015D  Happiness for all
[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/wpcontent/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 c_{1}, c_{2}, ..., c_{m} with m ≥ 2 such that c_{1} = i, c_{m} = j and there is a highway between cities c_{k} and c_{k+1} for k = 1, 2, ..., m1.
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 ≤ 10^{5}), 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:
20160712 13:54:57
Dfs with some logic ;)


Daksh:
20151223 19:06:31
dfs :) 

Oasis:
20151106 09:01:27
Easy One..Take care that there are multiple test cases...costed me 1 WA 
Added by:  Fidel Schaposnik 
Date:  20151028 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Argentinian Programming Tournament 2015 