题目描述

在直角坐标系上有 $n$（$n\le5000$）座塔。

要求把这些塔分成两组，使得同组内的两座塔的曼哈顿距离的最大值最小，并求出在此前提下求出有多少种分组方案，对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $x,y$，$0 \le x,y \le 5000$。

输出格式

第一行输出答案的最小值。

第二行输出分组方案数，对 $10^9+7$ 取模。

2
0 0
1 1

0
2

4
0 0
0 1
1 0
1 1

1
4

3
0 0
1000 1000
5000 5000

2000
2