测试数据来自 system/1624

描述

【版权说明】
本题为改编题。

【问题描述】
我国仍有许多贫困地区，解决这些地区的贫困问题，首先要从修路开始，接着是架设电网。

现有某贫困县借助中央拨款已建设了公路，该县电力部门在该县的某位置建起了一个发电站，准备从这个发电站开始建立该县的电网。已知架设电线的时候，只能从已经通电的地方架设电线到它相邻的地方（对角线不叫相邻），每个地方都有一个价值，为此处通电的价值，各个地方的价值不同，比如居民区的价值就比较高。

由于经费紧张，第一期工程中发电站只能让包括其本身所在区域的n个区域通电。同时，发电站还有一幅该县的地图，经过专家分析后得到了该县各个地方通电的价值。专家们把这幅地图划分成了x*y的方格，每个方格代表一个地方，其中发电站所在的方格的通电价值为1000，其他地方的通电价值为0到999之间的一个整数。

你作为富有爱心的新一代，愿意支持该项目，那么请你帮发电站计算一下，架设电线使n个区域通电后可以得到的最大价值是多少，并告诉发电站有多少种架设方法可以得到最大价值。由于该县人民都急切地盼望着通电，所以你的程序不能运行太久浪费时间，它的运行时间不能超过一秒。

格式

输入格式

输入文件的第一行是3个正整数：x,y,n。

第二行到第x+1行是一个x*y的矩阵，对应地图上各个地方的通电价值，其中通电价值为1000的是发电站。矩阵中每行的每两个相邻的数之间有一个空格。

输出格式

输出文件包括两行：第一行是一个整数，为n个区域通电后的最大价值；第二行是一个整数，为得到最大价值的架设电线的不同方法数（如果架设的终点是同一个地方并有多种方法且其中有不止一种方法可以得到最大价值，则算多种方法。如下图）。

（友情提示：请复制到记事本中查看）
地图：
1 2 3
1 1000 2
1 1 1
n=3，则有两种方法可以得到最大值：一种是发电站先往上扩展再往右扩展；第二种是先往右再往上，两种方法的终点都是最右上角价值为3的地区，但这是两种不同的方法，所以这样的地图应该输出1005和2。

样例1

样例输入1

3 3 5
8 3 8
5 1000 5
6 3 6

样例输出1

1026
1

限制

各个测试点1s

提示

【数据范围】
对于20%的数据，1<=x,y<=50;1<=n<=5。

对于50%的数据，1<=x,y<=100;1<=n<=10。

对于100%的数据，1<=x,y<=500;1<=n<=20。

来源

HOI 2009