Problem Statement  
A king of a mystical land likes to wear very tall shoes.
The tall shoes are sometimes an inconvenience as they make traveling through the kingdom's road network difficult.
There are N cities in the kingdom.
The cities are numbered 0 through N1.
The road network in the kingdom is connected: it is possible to get from any city to any other city by taking one or more roads.
Each road in the network is bidirectional and connects two different cities.
You are given the description of the road network in three int[]s: X, Y, and height, each with the same number of elements.
For each valid i, there is a road that connects cities X[i] and Y[i].
The value height[i] is the height limit for that road:
The king can travel along that road if and only if the height of his shoes is height[i] or less.
The king wants to walk from city 0 to city N1.
While doing so, he wants to wear shoes that are as tall as possible.
Before he goes for the walk, he can increase the height limits for some roads.
The king has a budget of B dollars for the modifications.
Increasing the height limit of any road by k costs k^2 dollars.
The height limit of each road can only be increased at most once.
You are given the int N, the int[]s X, Y and height, and the long B.
Compute the maximum height of shoes the king may wear for his walk from city 0 to city N1 after increasing the height limits appropriately.
  Definition   Class:  TallShoes  Method:  maxHeight  Parameters:  int, int[], int[], int[], long  Returns:  int  Method signature:  int maxHeight(int N, int[] X, int[] Y, int[] height, long B)  (be sure your method is public) 
    Constraints    N will be between 2 and 50, inclusive.    from, to, height will have between N1 and N*(N1)/2 elements, inclusive.    Each element of X, Y will be between 0 and N1, inclusive.    For all i, X[i] != Y[i].    Each undirected edge X[i], Y[i] will appear at most once.    Each element of height will be between 0 and 10^6, inclusive.    The graph described by X and Y will be connected.    B will be between 0 and 10^15, inclusive.   Examples  0)    3  {0, 1, 0}  {1, 2, 2}  {3, 4, 2}  1 
 Returns: 4 
In this example there are three roads: 01 (height limit 3), 12 (height limit 4), and 02 (height limit 2).
The king has a budget of 1 dollar.
The optimal way to use that budget is to increase the height limit for the 01 road from 3 to 4.
After that change, the king can use shoes of height 4 and walk along the path 012.


 1)    3  {0, 1, 0}  {1, 2, 2}  {3, 4, 2}  52 
 Returns: 9  Here we can increase the last road's height by 7 which will allow the king to wear shoes of height 9. Note that the king is not required to spend the entire budget. 

 2)    8  {0, 0, 3, 3, 4, 4, 4, 7, 7}  {1, 2, 1, 2, 3, 5, 6, 5, 6}  {1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000}  3 
 Returns: 2  
 3)    10  {0,1,2,3,4,5,6,7,8}  {1,2,3,4,5,6,7,8,9}  {0,0,0,0,0,0,0,0,0}  9876543210123 
 Returns: 1047565  
 4)    6  {0,0,0,0,0,1,1,1,1,2,2,2,3,3,4}  {1,2,3,4,5,2,3,4,5,3,4,5,4,5,5}  {999999,986588,976757,988569,977678,999999,967675,947856,955856,999999,975956,956687,999999,979687,999999}  0 
 Returns: 999999  

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.
