CF363E.Two Circles

Let's assume that we are given an n × m table filled by integers. We'll mark a cell in the i-th row and j-th column as (i, j). Thus, (1, 1) is the upper left cell of the table and (n, m) is the lower right cell. We'll assume that a circle of radius r with the center in cell (_i_0, _j_0) is a set of such cells (i, j) that . We'll consider only the circles that do not go beyond the limits of the table, that is, for which r + 1 ≤ _i_0 ≤ n - r and r + 1 ≤ _j_0 ≤ m - r.

A circle of radius 3 with the center at (4, 5).

Find two such non-intersecting circles of the given radius r that the sum of numbers in the cells that belong to these circles is maximum. Two circles intersect if there is a cell that belongs to both circles. As there can be more than one way to choose a pair of circles with the maximum sum, we will also be interested in the number of such pairs. Calculate the number of unordered pairs of circles, for instance, a pair of circles of radius 2 with centers at (3, 4) and (7, 7) is the same pair as the pair of circles of radius 2 with centers at (7, 7) and (3, 4).

假设我们有一个 $n \times m$ 的整数表格。我们将第 $i$ 行、第 $j$ 列的单元格记为 $(i,\,j)$。因此，$(1,\,1)$ 是表格的左上角单元格，$(n,\,m)$ 是右下角单元格。我们定义以单元格 $(i_0,\,j_0)$ 为中心、半径为 $r$ 的圆为所有满足条件的单元格 $(i,\,j)$ 的集合：

我们仅考虑不超出表格边界的圆，即满足 $r + 1 \le i_0 \le n - r$ 且 $r + 1 \le j_0 \le m - r$ 的圆。

以 $(4,\,5)$ 为中心、半径为 $3$ 的圆。

请找出两个互不相交（即不存在同时属于两个圆的单元格）且半径均为给定值 $r$ 的圆，使得这两个圆所覆盖的所有单元格中的数字之和最大。若存在多个能取得该最大和的圆对，则还需计算这样的圆对的数目。注意：此处统计的是无序圆对的个数；例如，以 $(3,\,4)$ 和 $(7,\,7)$ 为中心、半径为 $2$ 的两个圆构成的圆对，与以 $(7,\,7)$ 和 $(3,\,4)$ 为中心、半径为 $2$ 的圆对视为同一对。

The first line contains three integers n, m and r (2 ≤ n, m ≤ 500, r ≥ 0). Each of the following n lines contains m integers from 1 to 1000 each — the elements of the table. The rows of the table are listed from top to bottom at the elements in the rows are listed from left to right. It is guaranteed that there is at least one circle of radius r, not going beyond the table limits.

第一行包含三个整数 $n$、$m$ 和 $r$（$2 \leq n, m \leq 500$，$r \geq 0$）。接下来的 $n$ 行每行包含 $m$ 个整数，取值范围为 $1$ 到 $1000$ —— 即表格的元素。表格的行按从上到下的顺序给出，每行内的元素按从左到右的顺序给出。保证存在至少一个半径为 $r$ 的圆，且该圆完全位于表格边界之内。

Print two integers — the maximum sum of numbers in the cells that are located into two non-intersecting circles and the number of pairs of non-intersecting circles with the maximum sum. If there isn't a single pair of non-intersecting circles, print 0 0.

输出两个整数——两个不相交圆内格子中数字之和的最大值，以及达到该最大和的不相交圆对的数量。如果不存在任何一对不相交的圆，则输出 0 0。