{"raw_statement":[{"iden":"statement","content":"In a far away kingdom lives a very greedy king. To defend his land, he built _n_ guard towers. Apart from the towers the kingdom has two armies, each headed by a tyrannical and narcissistic general. The generals can't stand each other, specifically, they will never let soldiers of two armies be present in one tower.\n\nDuring defence operations to manage a guard tower a general has to send part of his army to that tower. Each general asks some fee from the king for managing towers. As they live in a really far away kingdom, each general evaluates his fee in the following weird manner: he finds two remotest (the most distant) towers, where the soldiers of his army are situated and asks for the fee equal to the distance. Each tower is represented by a point on the plane with coordinates (_x_, _y_), and the distance between two points with coordinates (_x_1, _y_1) and (_x_2, _y_2) is determined in this kingdom as |_x_1 - _x_2| + |_y_1 - _y_2|.\n\nThe greedy king was not exactly satisfied with such a requirement from the generals, that's why he only agreed to pay one fee for two generals, equal to the maximum of two demanded fees. However, the king is still green with greed, and among all the ways to arrange towers between armies, he wants to find the cheapest one. Each tower should be occupied by soldiers of exactly one army.\n\nHe hired you for that. You should find the minimum amount of money that will be enough to pay the fees. And as the king is also very scrupulous, you should also count the number of arrangements that will cost the same amount of money. As their number can be quite large, it is enough for the king to know it as a remainder from dividing by 109 + 7.\n\nTwo arrangements are distinct if the sets of towers occupied by soldiers of the first general are distinct."},{"iden":"input","content":"The first line contains an integer _n_ (2 ≤ _n_ ≤ 5000), _n_ is the number of guard towers. Then follow _n_ lines, each of which contains two integers _x_, _y_ — the coordinates of the _i_\\-th tower (0 ≤ _x_, _y_ ≤ 5000). No two towers are present at one point.\n\nPretest 6 is one of the maximal tests for this problem."},{"iden":"output","content":"Print on the first line the smallest possible amount of money that will be enough to pay fees to the generals.\n\nPrint on the second line the number of arrangements that can be carried out using the smallest possible fee. This number should be calculated modulo 1000000007 (109 + 7)."},{"iden":"examples","content":"Input\n\n2\n0 0\n1 1\n\nOutput\n\n0\n2\n\nInput\n\n4\n0 0\n0 1\n1 0\n1 1\n\nOutput\n\n1\n4\n\nInput\n\n3\n0 0\n1000 1000\n5000 5000\n\nOutput\n\n2000\n2"},{"iden":"note","content":"In the first example there are only two towers, the distance between which is equal to 2. If we give both towers to one general, then we well have to pay 2 units of money. If each general receives a tower to manage, to fee will be equal to 0. That is the smallest possible fee. As you can easily see, we can obtain it in two ways."}],"translated_statement":[{"iden":"statement","content":"在一个遥远的王国里，住着一位极其贪婪的国王。为了保卫他的领土，他建造了 #cf_span[n] 座瞭望塔。除了塔楼之外，王国还有两支军队，每支都由一位暴虐且自恋的将军统帅。这两位将军互相厌恶，具体来说，他们绝不会允许两支军队的士兵同时出现在同一座塔中。\n\n在防御行动中，为了管理一座瞭望塔，一位将军必须派遣他军队的一部分士兵前往该塔。每位将军都会向国王索取管理塔楼的费用。由于他们生活在极其遥远的王国，每位将军以一种奇特的方式评估自己的费用：他会找出自己军队士兵所驻守的两座最远的塔（即距离最远的两座塔），并索要等于这两座塔之间距离的费用。每座塔被表示为平面上的一个点 #cf_span[(x, y)]，而该王国中两点 #cf_span[(x1, y1)] 和 #cf_span[(x2, y2)] 之间的距离定义为 #cf_span[|x1 - x2| + |y1 - y2|]。\n\n这位贪婪的国王对将军们的要求并不完全满意，因此他只同意支付一笔费用，金额为两位将军所索要费用中的最大值。然而，国王依然贪得无厌，他希望在所有将塔楼分配给两支军队的方式中，找到花费最少的一种。每座塔必须恰好由一支军队的士兵驻守。\n\n他雇佣了你来解决这个问题。你需要找出支付将军费用所需的最少金额。同时，由于国王也非常细致，你还需计算出有多少种分配方案能达到这个最小费用。由于这个数字可能很大，国王只需要知道它对 #cf_span[109 + 7] 取模后的余数即可。\n\n两种分配方案不同，当且仅当第一支将军所占领的塔楼集合不同。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 5000])，表示瞭望塔的数量。接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[x, y] —— 第 #cf_span[i] 座塔的坐标 #cf_span[(0 ≤ x, y ≤ 5000)]。没有两座塔位于同一点。\n\n预测试 6 是本题的最大测试用例之一。\n\n第一行输出能够支付将军费用的最小金额。\n\n第二行输出能够以最小费用实现的分配方案数量。该数字需对 #cf_span[1000000007] (#cf_span[109 + 7]) 取模。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 5000])，表示瞭望塔的数量。接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[x, y] —— 第 #cf_span[i] 座塔的坐标 #cf_span[(0 ≤ x, y ≤ 5000)]。没有两座塔位于同一点。预测试 6 是本题的最大测试用例之一。"},{"iden":"output","content":"第一行输出能够支付将军费用的最小金额。\n\n第二行输出能够以最小费用实现的分配方案数量。该数字需对 #cf_span[1000000007] (#cf_span[109 + 7]) 取模。"},{"iden":"examples","content":"输入\n2\n0 0\n1 1\n输出\n0\n2\n\n输入\n4\n0 0\n0 1\n1 0\n1 1\n输出\n1\n4\n\n输入\n3\n0 0\n1000 1000\n5000 5000\n输出\n2000\n2"},{"iden":"note","content":"在第一个例子中，只有两座塔，它们之间的距离为 2。如果我们把两座塔都交给一位将军，那么我们需要支付 2 单位的钱。如果每位将军各管理一座塔，则费用为 0。这是可能的最小费用。如你所见，我们可以通过两种方式实现这一最小费用。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 2 $, be the number of guard towers.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} $ be a set of points in $ \\mathbb{Z}^2 $, where $ p_i = (x_i, y_i) $, with $ 0 \\leq x_i, y_i \\leq 5000 $, and all points are distinct.  \nThe distance between two points $ p_i = (x_i, y_i) $ and $ p_j = (x_j, y_j) $ is the Manhattan distance:  \n$$\nd(p_i, p_j) = |x_i - x_j| + |y_i - y_j|\n$$\n\n**Constraints**  \nEach tower must be assigned to exactly one of two armies (General A or General B).  \nLet $ A \\subseteq P $ be the set of towers assigned to General A, and $ B = P \\setminus A $ the set assigned to General B.  \nBoth $ A $ and $ B $ must be non-empty.\n\nFor a given assignment $ (A, B) $:  \n- The fee for General A is $ \\max_{p_i, p_j \\in A} d(p_i, p_j) $ (diameter of $ A $).  \n- The fee for General B is $ \\max_{p_i, p_j \\in B} d(p_i, p_j) $ (diameter of $ B $).  \n- The total cost is $ \\max(\\text{diam}(A), \\text{diam}(B)) $.\n\n**Objective**  \nFind:  \n1. The minimum possible value of $ \\max(\\text{diam}(A), \\text{diam}(B)) $ over all valid partitions $ (A, B) $.  \n2. The number of partitions $ (A, B) $ achieving this minimum cost, modulo $ 10^9 + 7 $.","simple_statement":null,"has_page_source":false}