Description

小s在玩一款配对游戏。游戏规则如下：在一个有障碍的网格图中，有 $p$ 个男人和 $p$ 个女人。这些人分散在网格上。一个网格可以同时有多个人。每个人只能向上、下、左、右四个方向移动且移动一格需要 $t_i$ 的时间。同一个时间所有人可以一起移动。小s的目标是要使每个人都可以和一个异性单独待在同一个房间。

小s想知道最少需要多长时间才能达到目标。

Input Format

从文件 pair.in 读入数据

输入的第一行包含$3$个整数：$n, m, p$。$n$ 和 $m$ 是网格图的规模，$p$ 为男人或女人的个数。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串。其中 . 代表空地，# 表示障碍，无法行走。

接下来 $p+p$ 行，每行 $3$ 个整数：$x, y, t$ ， 分别表示每个人的位置和行走一格所需要的时间。前 $p$ 行描述男人，后 $p$ 行描述女人。

Output Format

向文件 pair.out 输出数据

输出仅有一行，表示最少需要的时间。如果无法完成目标，则输出-1。

Sample

样例输入1

4 4 3
....
.###
####
####
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
1 1 2

样例输出1

2

Hint

$30\%$ : $n, m \le 4$, $p \le 8$

$60\%$ : $n, m \le 12, p \le 8$

$100\%$ : $n, m \le 22, p \le n \times m, t \le 10^9$