Building a New Barn

After years of scrimping and saving, Farmer John has decided to build a new barn. He wants the barn to be as accessible as possible, and he knows the coordinates of the grazing spots of all $N$ cows ($2 \le N \le 10000$). Each grazing spot lies at integer coordinates $(X_i, Y_i)$ with $-10000 \le X_i \le 10000$ and $-10000 \le Y_i \le 10000$. The cows never graze in spots that are horizontally or vertically adjacent to one another.

The barn must also be placed at integer coordinates, and it cannot be on any cow's grazing spot. The inconvenience of the barn for a single cow is the Manhattan distance $|X - X_i| + |Y - Y_i|$, where $(X, Y)$ is the barn and $(X_i, Y_i)$ is that cow's grazing spot. Where should the barn be built so that the sum of the inconvenience over all cows is minimized?

• Line 1: a single integer $N$.
• Lines 2 to $N+1$: line $i+1$ contains two space-separated integers $X_i$ and $Y_i$, the grazing location of cow $i$.

• Line 1: two space-separated integers: the minimum possible total inconvenience, and the number of integer locations (none of which may coincide with a cow's grazing spot) at which the barn achieves this minimum.

In the sample (the first test case), the minimum total inconvenience is $10$, and there are four spots where the barn can achieve it: $(0, -1)$, $(0, 0)$, $(1, 0)$, and $(1, 1)$.