Trouble in Terrorist Town (or simply TTT), is a known multi-player videogame where one of the players has to be a traitor, and his objective is to kill all the other players. On the other hand, the rest of the players are innocents, and they have to kill the traitor. What makes this game so interesting is the fact that nobody knows neither who the traitor nor who the innocents are. Each player knows only his/her own alignment and no one else’s. A group of friends are playing TTT in a server called: RPC Knuths and Barjnes (this server is awesome). In the middle of the night the server changes the game’s map. In the new map, all the players begin in a port, and they have to rent boats to go to The Island, a beautiful island that is full of colored pixels and nice gifts. If the innocents get to arrive to The Island and kill the traitor, then they win the match, and of course, all of the gifts. However, if the traitor kills all the innocent players, then he will keep the gifts and the island for himself. Besides this, there’s also an extra obstacle, or difficulty, added to the traitor problem, and that is the fact that this server uses real money to rent the boats (this is a policy of the server’s administrator to win money). Obviously, the players don’t have tons of money to spend on the game, there for they will want to win all the prices without losing too much money. Before the game starts, all the friends talk about how to win this match, in other words, they make a strategy. Blackcore says his strategy: minimize the cost by renting only one boat, but Marvin says to him that this is not a good strategy, because if all players go inside the same boat, then the traitor would active a C4 explosive and they all could die and lose the match. Ph.D. Sith, the most experienced player, offers a better strategy. It is common for a player not to trust in one, or even a few of his friends, because there are always some of them who are quite annoying. Those are the relationships between players. Initially all the players trust each other, until a player x says explicitly that he does not trust another particular player y. • The players are going to make groups. • Each group will rent only one boat. • A group is made of players that trust each other. • Two groups could be fused, if and only if, at least one player of the first group trusts in other player of the second group, and vice versa. • A member of a group can invite in to other player he trusts. • An invited player is a player that has an invitation of a group but he hasn’t accepted it. • An invited player will accept the offer, if and only if, he trusts in at least one member of the group. • An invited player has the same rights that a member of a group, that is, he could invite in to other players that he trusts.
2/2 • If an invited player x accepts the offers, and the player y that invited him was an invited too, then y could now accept the invitation. • A player can be part of only one group. Ph.D. Sith has a nice idea, isn’t it? But the guys have a big problem, they only get a few seconds before the match starts, and the groups have to be created just before it all begins. Your mission, if you choose to accept it, is to create a computer program that solves this problem. Input The input consists of several test cases. A test case starts with a line that contains 2 integers N (2 ≤ N ≤ 5000) and T (0 ≤ T ≤ N2 − N), the number of players and the number of relationships, respectively. The following T lines will contain an integer x and y (1 ≤ x, y ≤ N ) that will specify the relationship between these two players, meaning that x doesn’t trust in y. The last line contains only one integer D, the cost to rent a single boat. Output Print the total cost of renting all boats with an end of line. Sample Input 46 14 21 23 34 41 42 3 Sample Output 3