Guard Towers

아주 먼 왕국에 매우 탐욕스러운 왕이 살고 있다. 그는 자신의 영토를 방어하기 위해 n개의 경비탑을 세웠다. 탑 외에도 왕국에는 두 군대가 있으며, 각 군대는 폭군이자 자기도취적인 장군이 지휘한다. 두 장군은 서로를 견디지 못하며, 특히 두 군대의 병사들이 한 탑에 함께 있는 것을 절대로 허용하지 않는다.

방어 작전 중 경비탑을 관리하려면 장군은 자신의 군대 일부를 그 탑으로 보내야 한다. 각 장군은 탑을 관리하는 대가로 왕에게 일정한 비용을 요구한다. 그들은 정말 먼 왕국에 살기 때문에, 각 장군은 다음과 같은 기묘한 방식으로 자신의 비용을 산정한다. 자기 군대의 병사들이 배치된 탑 중 서로 가장 멀리 떨어진 두 탑을 찾아, 그 거리에 해당하는 비용을 요구한다. 각 탑은 평면 위의 좌표 (x, y)인 점으로 나타내며, 이 왕국에서 좌표가 (x1, y1)와 (x2, y2)인 두 점 사이의 거리는 |x1 - x2| + |y1 - y2|로 정한다.

탐욕스러운 왕은 장군들의 이러한 요구가 썩 마음에 들지 않았기 때문에, 두 장군이 요구한 비용 중 최댓값과 같은 비용 하나만 지불하기로 했다. 하지만 왕은 여전히 탐욕에 눈이 멀어 있으므로, 탑들을 두 군대에 배정하는 모든 방법 중 가장 저렴한 것을 찾고자 한다. 각 탑은 정확히 한 군대의 병사들이 점유해야 한다.

왕은 이를 위해 당신을 고용했다. 비용을 지불하기에 충분한 최소 금액을 구해야 한다. 또한 왕은 매우 꼼꼼하므로, 같은 금액이 드는 배정 방법의 수도 세어야 한다. 그 수는 상당히 클 수 있으므로, 왕에게는 그 수를 109 + 7로 나눈 나머지만 알려 주면 충분하다.

첫 번째 장군의 병사들이 점유한 탑들의 집합이 서로 다르면 두 배정 방법은 서로 다르다.

첫 번째 줄에 정수 n (2 ≤ n ≤ 5000)이 주어지며, n은 경비탑의 수이다. 이어지는 n개의 줄에는 각각 두 정수 x, y가 주어지며, 이는 i-th번째 탑의 좌표이다 (0 ≤ x, y ≤ 5000). 같은 점에 두 탑이 존재하지 않는다.

사전 테스트 6은 이 문제의 최대 테스트 중 하나이다.

첫 번째 줄에 장군들에게 비용을 지불하기에 충분한 최소 금액을 출력한다.

두 번째 줄에 가능한 최소 비용으로 수행할 수 있는 배정 방법의 수를 출력한다. 이 수는 1000000007 (109 + 7)로 나눈 나머지로 계산해야 한다.

첫 번째 예제에는 탑이 두 개뿐이며, 두 탑 사이의 거리는 2이다. 두 탑을 모두 한 장군에게 주면 돈을 2단위 지불해야 한다. 각 장군이 탑 하나씩을 관리하게 되면 비용은 0이 된다. 이것이 가능한 최소 비용이다. 쉽게 알 수 있듯이, 이 비용을 두 가지 방법으로 얻을 수 있다.