CF741B Arpa's weak amphitheater and Mehrdad's valuable

Just to remind, girls in Arpa's land are really nice. Mehrdad wants to invite some Hoses to the palace for a dancing party. Each Hos has some weight $ w_{i} $ and some beauty $ b_{i} $ . Also each Hos may have some friends. Hoses are divided in some friendship groups. Two Hoses $ x $ and $ y $ are in the same friendship group if and only if there is a sequence of Hoses $ a_{1},a_{2},...,a_{k} $ such that $ a_{i} $ and $ a_{i+1} $ are friends for each $ 1

The first line contains integers $ n $ , $ m $ and $ w $ ( $ 1

Print the maximum possible total beauty of Hoses Mehrdad can invite so that no one gets hurt and the total weight doesn't exceed $ w $ .

In the first sample there are two friendship groups: Hoses $ {1,2} $ and Hos $ {3} $ . The best way is to choose all of Hoses in the first group, sum of their weights is equal to $ 5 $ and sum of their beauty is $ 6 $ . In the second sample there are two friendship groups: Hoses $ {1,2,3} $ and Hos $ {4} $ . Mehrdad can't invite all the Hoses from the first group because their total weight is $ 12>11 $ , thus the best way is to choose the first Hos from the first group and the only one from the second group. The total weight will be $ 8 $ , and the total beauty will be $ 7 $ .