《快乐农场5》的创作者决定发明奶牛放牧的机制。游戏中的奶牛动作非常缓慢,移动速度也非常缓慢,甚至可以认为它们是静止不动的。然而,肉食动物应该永远被赶走。
为此,一位年轻的玩家 Vasya 决定让牧羊人沿着同一条封闭路径绕着奶牛跑。非常重要的是,奶牛必须严格留在路径限制的区域内,否则迟早会有一些奶牛被吃掉。为了绝对确保奶牛的安全,Vasya 希望路径完成时间最短。
新游戏针对不同设备推出,包括手机。这就是为什么开发人员决定停止使用带有浮动小数点的算术,而只使用整数算术。游戏中的牛和牧羊人被表示为平面上具有整数坐标的点。比赛时间以轮次为模型。在每次转弯时,牧羊人都可以留在原地,也可以朝八个方向之一迈步:水平、垂直或对角线。由于坐标应始终保持整数,因此水平和垂直步长的长度等于 1,对角步长的长度等于 $$\sqrt{2}$$。牛一动也不动。你必须尽量减少牧羊人绕着整个牛群跑动的次数。
输入
第一行包含一个整数 N,表示牛群中奶牛的数量 (1 ≤ N ≤ 105)。接下来的 N 行中的每一行都包含两个整数 Xi 和 Yi,它们表示 (|Xi|, |Yi| ≤ 106) 中一头牛的坐标。多头牛可以站在一个点上。
输出
打印单个数字 — 所寻找路径中的最小移动次数。
示例
输入 #1
4 1 1 5 1 5 3 1 3
输出 #1
16
注意
示例测试图片:坐标网格涂成灰色,坐标轴涂成黑色,奶牛涂成红色,寻找的路线涂成绿色。