You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

寒假即将来临，SZY已经开始制定旅行计划了。他打算请你帮他找到最佳的旅行路线。

Description

已知有一张由 $n*m$ 个方格组成的矩形地图，图中每个方格表示具体的位置，每个方格有一个正整数的权值 $w_{i,j}$ 。地图左上角为$(1,1)$ ，右下角为 $(n,m)$ 。

已知 SZY 的当前位置 $(x_0,y_0)$ 和 长度为 $len$ 的关于旅行位置的序列 $(x_1,y_1), (x_2,y_2), … ,(x_{len},y_{len})$ ，表示他将从 $(x_0,y_0)$ 出发，依次经过 $(x_1,y_1),(x_2,y_2), … ,(x_{len},y_{len})$ ，最后回到 $(x_0,y_0)$。

关于 最佳路线 的定义如下：

• 路线的起点和终点均为 $(x_0,y_0)$， 并且 序列 $ (x_0,y_0),(x_1,y_1),(x_2,y_2), … ,(x_{len},y_{len}),(x_0,y_0) $ 是关于路线的序列（包含起点和终点） $(x_0,y_0),(X_1,Y_1),(X_2,Y_2), … ,(x_0,y_0)$ 的子序列。

• 关于该路线的序列的点权和最小（对于重复经过的位置，点权和重复计算）。

请你分别计算出 最小的点权和 以及 满足该情况的路线数量 ， 路线数量对 $998244353$ 取模。

Format

Input

第一行三个整数 $ n,m,len( 1 \leq n,m \leq 300, 1 \leq len \leq 100) $ 。

第 2 到 n+1 行，每行 m 个整数，其中第 i+1 行为 $ w_{i,1},w_{i,2}, … ,w_{i,m} (1 \leq w_{i,j} \leq 10^9) $。

第 n+2 行到第 n+len+2 行，每行 2 个整数 ,其中第 n+2+i 行为 $x_i, y_i ( 1 \leq x_i \leq n, 1 \leq y_i \leq m)$ 。

Output

一行两个整数，分别表示 最小的点权和 以及 最佳路线数量 。

Samples

5 3 4
3 4 6 
1 5 3  
3 2 5 
10 28 33 
1 12 9  
2 2
1 1
3 3
5 1
3 2

56 1

3 3 1
3 3 3
3 3 3
3 3 3
1 1
3 3

27 36

Limitation

Time Limit: 4 second

Memory Limit: 256 MiB