题目背景

春节时，小z正在看一副中国地图，每个省都有各自的财富与能力，小z想到了一个问题，若这天，主席已光速超快的速度走遍天下，哪个省可以称为2025年中国最good省？

题目描述

不过，小z可不想让地图那么简单，毕竟zswdlqy还是很良心liang心的，小z会给你一幅n行m列的地图，当然并不是首都就是good。而每个省的道路情况不同，0代表是路，#表示障碍，说明遇到0则不能走。

关于good省评选，会根据能力的大小评选，但财富也有用，但得大于9999，会给能力×（财富除以10000），由于小z的良心liang心大发，又给你了一个任务，要求输出从首都，到good省有几条走法？

首都在第一个省，编号为1

输入格式

第一行输入n,m,k(k表示有k个省) 一直到第n+1行输入完n行m列的地图（每次输入的是该省的编号） 下来k行，每行输入两个数，表示该省的财富与能力。

输出格式

输出good省的编号与到它有几条走法？

样例

4 5 3
0 0 1 0 0
2 # 3 0 0
0 0 0 # #
0 # 0 0 0
10000000 1
100 1
500000 100

3
4

数据规模与约定

对于100%的数据保证$1\le 财富，能力 \le 1e9; 1 \le 题中其他数据 \le 1000$