在一个遥远的王国里住着一位非常贪婪的国王。为了保卫他的土地,他建造了n座守卫塔。除了塔楼之外,王国还有两支军队,每支军队都由一位残暴且自恋的将军领导。将领们互相看不惯,具体来说,就是绝对不会让两军士兵同处一塔。
在管理守卫塔的防御行动中,将军必须派遣部分军队到该塔。每位将军都会向国王索要一些管理塔楼的费用。由于他们生活在一个非常遥远的王国,每个将军都以以下奇怪的方式评估他的费用:他找到两座最偏远(最远)的塔楼,那里是他军队的士兵所在的位置,并要求与距离相等的费用。每个塔都由平面上坐标为 (x, y) 的点表示,坐标为 (x1, y1) 和 (x2, y2) 的两点之间的距离在该王国中确定为 |x1 - x2| + |y1 - y2|。
贪婪的国王对将军们的这样的要求并不满意,所以他只同意为两名将军支付一笔费用,相当于最多两次要求的费用。然而,国王仍然贪得无厌,在军队之间布置塔楼的所有方法中,他想找到最便宜的一种。每个塔只能由一支军队的士兵占领。
他为此雇用了你。您应该找到足以支付费用的最低金额。而且国王也很谨慎,你也应该数一下需要花同样钱的安排有多少。由于它们的数量可能相当大,国王只要知道除以 109 + 7 的余数就足够了。
如果第一位将军的士兵占据的塔组不同,则两种排列是不同的。
输入
第一行包含一个整数n(2≤n≤5000),n是警卫塔的数量。接下来是 n 行,每行包含两个整数 x、y——第 i 个塔的坐标 (0 ≤ x, y ≤ 5000)。同一地点不存在两座塔。
预测试 6 是此问题的最大测试之一。
输出
在第一行打印足以向将军支付费用的尽可能少的金额。
在第二行写出可以使用尽可能少的费用进行的安排数量。该数字应以 1000000007 (109 + 7) 为模进行计算。
示例
输入 #1
2 0 0 1 1
输出 #1
0 2
输入 #2
4 0 0 0 1 1 0 1 1
输出 #2
1 4
输入 #3
3 0 0 1000 1000 5000 5000
输出 #3
2000 2
注意
在第一个例子中,只有两座塔,它们之间的距离等于 2。如果我们将两座塔都给一个将军,那么我们就必须支付 2 个单位的钱。如果每个将军都接收一座塔来管理,则费用将等于0。这是可能的最小费用。正如您所看到的,我们可以通过两种方式获取它。