P3632 [APIO2011] 寻路

TooDee 是一块二维格子状的土地（就像著名的笛卡尔坐标系那样），在这里生活着很多可爱的 Dee。Dee 是像蜜蜂一样的小动物，它们只在二维活动，而且他们非常的 文明开化。TooDee 的蜂窝和正常世界的蜂窝也是很不一样的，他们是矩形的且它们的边平行于 TooDee 的地理坐标系，就是说矩形的边或者是东西走向， 或者是南北走向。 因为 Dees 是很高级的生物，他们有很多固定的飞行轨道，这些轨道由一些平行于坐标轴的线段组成，线段只会在经纬度都是整数的点相交。Dee 在 TooDee 飞行时必须遵守以下规则（请记住 TooDee 中所有点的经纬度都是整数）： 1. 如果当前在点 $(X, Y)$，则下一步只能飞到四个邻点 $(X, Y - 1), (X, Y + 1), (X - 1, Y), (X + 1, Y)$； 2. 不可以进入蜂巢； 3. 只能在蜂巢的角上或者边上改变飞行方向； 4. 开始的时候可以向任何方向飞； 今晚是公共财政大臣 Deeficer 的女儿的生日，她想尽早回家，请帮她找到最快的回家路径。假设她每秒可以飞行一个单位的距离。

无

无

对于 $20\%$ 的测试数据，$n\leq 10$，所有的坐标都是小于 $100$ 的非负整数； 对于 $60\%$ 的测试数据，$n\leq 100$，所有坐标的绝对值都小于 $10^3$； 对于 $100\%$ 的测试数据，$0\leq n\leq 10^3$，所有坐标的绝对值都是不超过 $10^9$ 的整数。