Optimal Barn Placement

After years of saving, Farmer John is ready to build a new barn. He has the coordinates of the grazing spots of all N cows. Each grazing spot is at an integer coordinate ( (x_i, y_i) ) (with ( -10000 \le x_i,y_i \le 10000 )). The cows never graze on spots that are horizontally or vertically adjacent. The barn must be built at integer coordinates and cannot coincide with any cow's grazing spot. The inconvenience for each cow is defined by the Manhattan distance [ |X - x_i| + |Y - y_i| ] where ( (X, Y) ) is the barn's location. Your task is to choose a valid location for the barn that minimizes the total inconvenience (i.e. the sum of Manhattan distances from the barn to each cow). Let ( ans1 ) be this minimum total Manhattan distance and ( ans2 ) be the number of valid barn locations achieving ( ans1 ).

Note:

• If \( N \) is even, then the optimal locations for \( X \) lie in the closed interval \([a, b]\), where \( a\) and \( b\) are the two medians of the \( x\)-coordinates. Similarly, the optimal \( Y \) values lie in an interval \([c, d]\) from the \( y \)-coordinates. Thus, the total number of unconstrained optimal points is \((b - a + 1) \times (d - c + 1)\). However, you must exclude any points that are exactly a cow's grazing spot.
• If \( N \) is odd, the unconstrained unique optimum would be the median point \((m_x, m_y)\), but since one cow occupies that point, it is not allowed. In that case, the best valid locations are exactly those four points that are one unit away horizontally or vertically from \((m_x, m_y)\), each incurring an extra cost of 1.

inputFormat

The first line contains an integer \( N \) (\(2 \le N \le 10000\)), the number of cows. Each of the following \( N \) lines contains two space‐separated integers \( x_i \) and \( y_i \) (\( -10000 \le x_i, y_i \le 10000 \)), representing the coordinates of a cow's grazing spot. It is guaranteed that no two grazing spots are horizontally or vertically adjacent.

outputFormat

Output two integers: \( ans1 \), the minimized total Manhattan distance, and \( ans2 \), the number of valid barn locations that achieve this minimum.

sample

3
0 0
2 2
4 4

9 4