Problem: The city of Kyoto is a famous tourist destination for old temples and shrines.

Ikta came to Kyoto sightseeing with a few friends, but as a result of all acting freely, they all got lost.

So Ikta decided to think about where to meet in order to meet everyone as soon as possible.

Kyoto's roads run innumerably at intervals of 10 from east to west and north to south, and can be regarded as an infinitely wide square grid.

Roads are considered straight and have no width. In addition, the position moved by a distance x to the east and a distance y to the north with respect to the center of the city is represented by the coordinates (x, y).

At the center of the city (0,0), the east-west road and the north-south road intersect.

The figure below illustrates the roads of Kyoto and the coordinates of some points.


<image>


Since the coordinates (Xi, Yi) of N tourists are given as integers, answer the minimum time required for N people to move on the road and gather at one point.

Tourists can move continuously on the road at a speed of 1 distance per hour.

The coordinates of the N tourists given are different, and all coordinates are guaranteed to be on the road.

It is also possible for multiple tourists to exist at one point at the same time, or for tourists to move so that they pass each other.



Input

The input is given in the following format.

> N
> X1 Y1
> ...
> XN YN
>

N in the first line is the number of tourists. The i-th line (1 ≤ i ≤ N) of the next N lines represents the location of the i-th tourist (Xi, Yi). Xi and Yi are given as integers, respectively.

Constraints

Each variable being input satisfies the following constraints.

* 2 ≤ N ≤ 10000
* −108 ≤ Xi, Yi ≤ 108
* When i ≠ j (Xi, Yi) ≠ (Xj, Yj)
* At least one of Xi and Yi is a multiple of 10.

Output

Print the solution to the problem on one line. Allows absolute error up to 10-3.

Examples

Input

3
5 10
-10 0
3 -10


Output

14


Input

2
0 0
0 1


Output

0.5


Input

4
100000000 100000000
100000000 -100000000
-100000000 100000000
-100000000 -100000000


Output

200000000

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

long long N, X[1 << 18], Y[1 << 18]; vector<long long>P, Q, V1, V2;

long long dist(long long px, long long py, long long qx, long long qy) {
	if (px == qx && px % 20 == 0) return abs(py - qy);
	if (py == qy && py % 20 == 0) return abs(px - qx);

	long long ans = 0;

	if (px % 20 == 0 && qx % 20 == 0) {
		if ((py / 20) == (qy / 20)) {
			long long V1 = abs(px - qx);
			long long A1 = py - ((py / 20) * 20), A2 = qy - ((qy / 20) * 20);
			V1 += min(A1 + A2, 40LL - (A1 + A2));
			ans = V1;
		}
		else ans = abs(px - qx) + abs(py - qy);
	}
	else if (py % 20 == 0 && qy % 20 == 0) {
		if ((px / 20) == (qx / 20)) {
			long long V1 = abs(py - qy);
			long long A1 = px - ((px / 20) * 20), A2 = qx - ((qx / 20) * 20);
			V1 += min(A1 + A2, 40LL - (A1 + A2));
			ans = V1;
		}
		else ans = abs(px - qx) + abs(py - qy);
	}
	else {
		ans = abs(px - qx) + abs(py - qy);
	}
	return ans;
}

long long solve(long long px, long long py) {
	long long sum = 0;
	for (int i = 0; i < N; i++) {
		sum = max(sum, dist(px, py, X[i], Y[i]));
	}
	return sum;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i]; X[i] *= 2; Y[i] *= 2;
		X[i] += 200000000; Y[i] += 200000000;
		P.push_back(X[i] + Y[i]);
		Q.push_back(X[i] - Y[i]);
	}
	sort(P.begin(), P.end());
	sort(Q.begin(), Q.end());
	long long CX = (P[0] + P[N - 1]) / 2;
	long long CY = (Q[0] + Q[N - 1]) / 2;
	long long DX = (CX + CY) / 2;
	long long DY = CX - DX;

	for (int i = -100; i <= 100; i++) V1.push_back(DX + i);
	for (int i = -100; i <= 100; i++) V2.push_back(DY + i);

	long long minx = (1LL << 60);
	for (int i = 0; i < V1.size(); i++) {
		for (int j = 0; j < V2.size(); j++) {
			if (!(V1[i] % 20 == 0 || V2[j] % 20 == 0)) continue;
			minx = min(minx, solve(V1[i], V2[j]));
		}
	}
	printf("%.12Lf\n", 0.5L * minx);
	return 0;
}