假设我们有一个由整数填充的 n × m 表。我们将第 i 行第 j 列中的单元格标记为 (i, j)。因此,(1, 1) 是表格的左上单元格,(n, m) 是右下单元格。我们假设以单元格 (i0, j0) 为中心、半径为 r 的圆是一组此类单元格 (i, j),且 $$\sqrt{(i-i_{0})^{2}+(j-j_{0})^{2}} \leq r$$。我们将仅考虑不超出表格限制的圆,即 r + 1 ≤ i0 ≤ n - r 和 r + 1 ≤ j0 ≤ m - r。
半径为 3、圆心位于 (4, 5) 的圆。
找到两个给定半径 r 的不相交圆,使得属于这些圆的单元格中的数字之和最大。如果存在属于两个圆的单元格,则两个圆相交。由于可以有不止一种方法来选择一对具有最大总和的圆,因此我们也会对此类对的数量感兴趣。计算无序圆对的数量,例如,一对圆心为 (3, 4) 和 (7, 7) 、半径为 2 的圆与圆心为 (7, 7) 和 (3, 4) 、半径为 2 的圆对是同一对。
输入
第一行包含三个整数 n、m 和 r (2 ≤ n, m ≤ 500, r ≥ 0)。以下 n 行中的每一行都包含 m 个从 1 到 1000 的整数 — 表的元素。表的行从上到下列出,行中的元素从左到右列出。保证至少有一个半径为r的圆,且不超出表的限制。
输出
打印两个整数 — 位于两个不相交圆的单元格中数字的最大和以及具有最大和的不相交圆对的数量。如果没有一对不相交的圆,则打印 0 0。
示例
输入 #1
2 2 0 1 2 2 4
输出 #1
6 2
输入 #2
5 6 1 4 2 1 3 2 6 2 3 2 4 7 2 5 2 2 1 1 3 1 4 3 3 6 4 5 1 4 2 3 2
输出 #2
34 3
输入 #3
3 3 1 1 2 3 4 5 6 7 8 9
输出 #3
0 0