Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Preparing for War

By Peregrine_Falcon · Limits 2s, 512 MB

There were N cities in England. Each contained a warrior with skillset equal to X. All the cities were connected with M bi-directed roads. Initially all pairs of cities were connected through one or more paths.

Vikings attacked England. You know vikings are well known for their excellent war strategy. In the first attack, Vikings selected some cities and destroyed them. They are now preparing to attack the capital. All the soldiers from the destroyed cities died after the first attack. When a city is destroyed, all the roads connecting the city also destroyed.

Vikings destroyed all such cities C that if and only if there are two city locations A and B such that to go from one to another (A to B or B to A), a person must pass through a location C. It is possible that in some cases no such city C exists.

After the sudden attack, the king of England planned to defend the capital. But due to limited capacity of capital, the king can choose only K solders. The king wants to build an army as strong as possible.

After the first attack, some cities are still connected to one another. He will select at most one soldier from each of those connected components of cities. He will choose exactly K soldiers with maximum skill set value.

You have to find the maximum possible summation of skillset for K soldiers. Assume that after the first attack it is still possible to choose K soldiers.


First line of input contains three integers N , M and K (1 <= K <= N <= M <= 500000) M lines follows contains two integers U and V (U != V). These two cities U and V are connected by a road. Next line will contain N integers separated by space. The ith integer means the skillset X (1 <= X <= 1000000) of the soldier from ith city.


Print one integer - the maximum possible summation of skillset for K soldiers.


7 7 2
1 2
2 3
3 6
6 7
3 7
3 4
4 5
7 10 5 3 1 4 11



95% Solution Ratio

notredEarliest, 3M ago

moiddaFastest, 0.3s

NJRafiLightest, 69 MB

NJRafiShortest, 1687B


Login to submit

Related Contests