Problem Statement   Bearland consists of N cities, numbered 0 through N1.
For each i, city i is inhabited by x[i] citizens.
You are given the int[] x with N elements.
There are M bidirectional roads.
Each road connects two different cities.
No two roads connect the same pair of cities.
Do you know that feeling when your fridge is full and you still don't know what to eat (and you eventually order a pizza)?
The citizens of Bearland have the same feeling whenever they have to choose from too many roads.
Thus, the road network in Bearland was designed in such a way that every city is incident to at most three roads.
In other words, each city is directly connected to at most three other cities.
You are given the description of the road network: the int[]s a and b with M elements each.
For each valid i, there is a road that connects cities a[i] and b[i].
All roads in Bearland were built a long time ago and their current condition is quite bad.
Limak, a public transport inspector, can choose a few of the existing roads and renovate them.
You are given the int K: the maximum number of roads Limak can renovate.
After the renovation, each citizen will be happy if and only if at least one of the roads from their city was renovated.
Find and return the maximum number of happy citizens.   Definition   Class:  BearKRoads  Method:  maxHappy  Parameters:  int[], int[], int[], int  Returns:  int  Method signature:  int maxHappy(int[] x, int[] a, int[] b, int K)  (be sure your method is public) 
    Notes    N will be between 2 and 1000, inclusive.    x will contain exactly N elements.    Each element in x will be between 1 and 999, inclusive.    M will be between 1 and 1000.    a and b will each contain exactly M elements.    Each element in a and in b will be between 0 and N1, inclusive.    No road will connect a city to itself.    No two roads will connect the same pair of cities.    Every city will be incident to at most three roads.    K will be between 1 and 7, inclusive.    K will not be greater than M.   Examples  0)    {10, 50, 50, 10}  {0, 1, 2}  {1, 2, 3}  1 
 Returns: 100  There are four cities and three roads: 01, 12 and 23.
We can only renovate at most one road.
It is optimal to renovate the road 12.
This makes 100 citizens happy. 

 1)    {10, 50, 50, 10}  {0, 1, 2}  {1, 2, 3}  2 
 Returns: 120  This is the same country but now we have K=2.
Now the optimal solution is to renovate the roads 01 and 23.
This makes all 120 citizens happy. 

 2)    {42, 100, 500}  {0, 1}  {1, 2}  2 
 Returns: 642  We can renovate both roads.
All 42 + 100 + 500 = 642 citizens will be happy. 

 3)    {42, 100, 500, 999, 999, 999, 999}  {0, 1}  {1, 2}  2 
 Returns: 642  
 4)    {969,467,808,263,179,428,595,557,406,80}  {5,4,9,7,9,3}  {4,0,8,8,0,1}  3 
 Returns: 2841  
 5)     6)    {1,2,3,4,2}  {0,0,0,1}  {1,2,3,4}  2 
 Returns: 9  
 7)    {8,18,14,10,7,16,4,19,6,12,17,10,12,3,15,8,15,12}  {0,15,1,5,7,3,17,4,15,3,13,14,4,7}  {8,10,16,13,2,10,2,10,11,13,0,9,3,6}  7 
 Returns: 173  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
