L - 机のしみ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

すぬけ君の机には N 個のしみがついている。 i 番目のしみの座標は (x_i, y_i) である。

すぬけ君は、しみを何個か (0 個でもよい) 付け足してしみ全体がボードゲームの盤面となるようにしたい。すぬけ君の作りたい盤は、ある K に対して、K^2 個のしみが K \times K の正方格子状に並んでいるようなものである。ただし、盤面が座標軸に平行である必要はない。

すぬけ君が書き足さなければならないしみの個数の最小値を求めよ。 ただし、机は十分広く、しみが机をはみ出すことはないものとする。

入力は整数であるが、新しく追加するしみの座標は整数でなくても良い。

Constraints

  • 1 \leq N \leq 100000
  • 0 \leq x_i, y_i \leq 10^9
  • 二つのしみが同じ座標にあることはない
  • 入力は全て整数である

Input Format

入力は以下の形式で標準入力から与えられる。 
N
x_1 y_1
:
x_N y_N

Output Format

答えを一行に出力せよ。

Sample Input 1

3
1 5
3 6
4 9

Sample Output 1

6
たとえば、(5, 7), (0, 7), (2, 8), (-1, 9), (1, 10), (3, 11) の六ヶ所にしみを付け足せばよい。