PROBLEM STATEMENT

John is obsessed with security.
He has several old houses and he wants to build one new.
John is very afraid of thieves, so he will choose the location of the new house using the 
following method.
From each of his old houses, he will measure the Manhattan distance to the new house.
He will then take the k-th (1 based) shortest distance.
The location that minimizes this distance will be the location of his new house.



You are given the locations of his old houses in vector <int>s x and y.
The i-th old house is located at (x[i], y[i]).
Return the smallest possible k-th distance.



DEFINITION
Class:TheNewHouseDivOne
Method:distance
Parameters:vector <int>, vector <int>, int
Returns:double
Method signature:double distance(vector <int> x, vector <int> y, int k)


NOTES
-The returned value must be accurate to within a relative or absolute value of 1E-9.
-The Manhattan distance between two points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.
-Several houses can be located at the same point.


CONSTRAINTS
-x will contain between 1 and 50 elements, inclusive.
-x and y will contain the same number of elements.
-Each element of x will be between -50 and 50, inclusive.
-Each element of y will be between -50 and 50, inclusive.
-k will be between 1 and the number of elements in x, inclusive.


EXAMPLES

0)
{-1, -1, 1, 1}
{-1, 1, -1, 1}
3

Returns: 2.0

One of the optimal ways is to build a new house at (0, 0).

1)
{-1, -1, 1, 1}
{-1, 1, -1, 1}
2

Returns: 1.0

And here we have four possible locations for the new house - (-1, 0), (1, 0), (0, -1) and (0, 1).

2)
{4, 4, 4, 4, 4, 3, 3, 5, 5}
{7, 7, 7, 4, 4, 5, 6, 5, 6}
9

Returns: 1.5

Some houses are located at the same point.

3)
{30, -15, 24, -23, 43, -8, -6, -47, 23, -11, 43, 6, -18, 44, -46, 16, 32, 31, 13, 9, 22, 25, 4, 
-44, 38, -41, -20, 41, -35, 7, 25, 39, -36, -20, -5, -38, -15, -22, 0}
{-45, -7, -33, 31, -8, -33, -20, -14, -50, -48, -31, 35, -24, -31, -11, 41, -41, -11, 46, -1, -5, 
5, -39, -26, -40, -9, 16, 38, -30, 34, 46, -17, -27, 33, -38, 28, 46, -16, -46}
13

Returns: 32.0

 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.