22452번 - 京都旅行 스페셜 저지다국어

キョウトという街は古い寺社仏閣で有名な観光地である。

イクタ君は数人の友人とキョウト観光に来ていたが、全員が好き勝手に行動した結果、みんな迷子になってしまった。

そこでイクタ君は、なるべく早く全員と合流するためには集合場所をどこにするのがよいか考えることにした。

キョウトの道路は東西と南北に距離10の間隔で無数に走っており、無限に広がる正方格子とみなすことができる。

道路は直線であるとみなし、幅は無いものとする。 また、街の中心を基準として東に距離$x$、北に距離$y$移動した位置を$(x,y)$という座標で表す。

街の中心である$(0,0)$では東西の道路と南北の道路が交差している。

下図はキョウトの道路と、いくつかの点の座標を図示したものである。

$N$人の観光客の座標$(X_{i},Y_{i})$が整数で与えられるので、$N$人が道路上を移動して1点に集合するのに必要な時間の最小値を答えよ。

観光客は時間1あたり距離1の速さで連続的に道路上を動くことができるとする。

与えられる$N$人の観光客の座標はそれぞれ相異なり、また全ての座標は道路上にあることが保証されている。

また、複数の観光客が同時に1点に存在したり、観光客同士がすれ違うように移動することも可能であるとする。

入力は以下の形式で与えられる。

$N$

$X_{1}$ $Y_{1}$

...

$X_{N}$ $Y_{N}$

1行目のNは観光客の人数である。 次のN行のうちi行目($1\leq i \leq N$)はi番目の観光客の位置$(X_{i}, Y_{i})$を表している。 $X_{i}$,$Y_{i}$はそれぞれ整数で与えられる。

問題の解を1行に出力せよ。 $10^{-3}$までの絶対誤差を許容する。

入力中の各変数は以下の制約を満たす。

• $2 \leq N \leq 10000$

• $-10^8 \leq X_{i}, Y_{i} \leq 10^8$

• $i \neq j$ のとき $(X_{i}, Y_{i}) \neq (X_{j}, Y_{j})$

• $X_{i}$ と $Y_{i}$ のうち少なくとも一方は10の倍数である