问题陈述
在须拔君的桌子上 N 个污渍附着着。 i 第个污渍的坐标是 (x_i, y_i) 是。
斯努克君想要再添加若干条污渍(0 条也可以),使所有污渍整体构成棋盘游戏的棋盘。斯努克君想制作的棋盘是由某个 K ,K^2 污渍 K \times K 排列成正方形网格状的图形。不过,棋盘面不必与坐标轴平行。
求出斯努克君必须补画的污渍数量的最小值。 但是,假设桌子足够宽,污渍不会超出桌面。
输入是整数,但新添加的污渍的坐标不必是整数。约束
- 1 \leq N \leq 100000
- 0 \leq x_i, y_i \leq 10^9
- 不会有两个污渍位于相同的坐标。
- 输入中的所有值都是整数。
输入格式
N x_1 y_1 : x_N y_N
输出格式
示例输入 1
3 1 5 3 6 4 9
示例输出 1
6