Optimal Pipeline Position

A petroleum company plans to build a main oil pipeline running from east to west. This pipeline must cross an oil field that contains \( n \) oil wells. From each oil well, a feeder pipeline will connect to the main pipeline via the shortest route (either heading north or south).

Each oil well is given by its \( x \) (east-west) and \( y \) (north-south) coordinates. The connection between a well and the main pipeline is a vertical (north-south) line. Thus, the extra pipeline length needed for a well located at \( y_i \) when the main pipeline is set at \( y = k \) is \( |y_i - k| \).

The objective is to determine the optimal north-south position \( k \) for the main pipeline so that the total length of the feeder pipelines, \[ S = \sum_{i=1}^{n} |y_i - k|, \] is minimized. It is known that the optimal \( k \) is the median of the \( y \) coordinates. (If \( n \) is even, any value between the two central values yields the same minimum total length; for this problem choose the lower median as the optimal location.)

You are given \( n \) and the coordinates for each of the oil wells. Compute the optimal main pipeline's position and the minimal total length required for the feeder pipelines.

inputFormat

The first line contains an integer \( n \) (\( 1 \leq n \leq 10^5 \)), the number of oil wells. Each of the following \( n \) lines contains two integers \( x \) and \( y \), denoting the coordinates of each oil well. Note that the \( x \) coordinate is provided but is not used in computing the optimal main pipeline position.

outputFormat

Output two integers separated by a space: the first is the optimal \( y \) coordinate (i.e. the median of the \( y \) values, choosing the lower median when \( n \) is even), and the second is the minimal total feeder pipeline length.

sample

3
1 2
2 3
3 1

2 2