集市是一个历史悠久的传统民间贸易活动，指在特定日期和固定地点举行的商品交易和社交聚会，具有独特的民俗和地域文化差异。

今天，你所在的城市正在举办端午节集市，你计划参观 $k$ 个摊位。具体来说，场地被组织成一个 $n \times m$ 的网格，包含 $n$ 行网格点，每行有 $m$ 个网格点，行与列之间的间距为 $1$。我们将左上角网格点的坐标记为 $(0, 0)$，右下角网格点的坐标记为 $(n-1, m-1)$。集市的入口位于 $(0, 0)$，出口位于 $(n-1, m-1)$。你需要从入口出发，以任意顺序访问这 $k$ 个摊位，最后到达出口。摊位设置在网格的边上，可以视为网格边上的点。形式上，每个摊位的坐标为 $(x, y)$，其中 $x$ 或 $y$ 为整数。

你需要在网格的边上移动，但集市人潮拥挤，你希望尽快完成参观。由于人群密度不同，沿每条边移动的速度也不同，你想知道从入口出发，访问所有 $k$ 个摊位并到达出口所需的最短时间。在摊位停留的时间忽略不计。

输入格式

第一行包含三个整数 $n, m, k$ ($2 \le n \le 50, 2 \le m \le 4, 1 \le k \le 10^5$)。

接下来的 $n$ 行，第 $i$ 行包含 $m-1$ 个整数 $v^h_{i,0}, v^h_{i,1}, \dots, v^h_{i,m-2}$ ($1 \le v^h_{i,j} \le 10^5$)，其中 $v^h_{i,j}$ 表示沿从 $(i-1, j)$ 到 $(i-1, j+1)$ 的水平边移动的速度。

接下来的 $n-1$ 行，第 $i$ 行包含 $m$ 个整数 $v^v_{i,0}, v^v_{i,1}, \dots, v^v_{i,m-1}$ ($1 \le v^v_{i,j} \le 10^5$)，其中 $v^v_{i,j}$ 表示沿从 $(i-1, j)$ 到 $(i, j)$ 的垂直边移动的速度。

接下来的 $k$ 行，每行包含两个实数 $x, y$ ($0 \le x \le n-1, 0 \le y \le m-1$)，表示你打算访问的摊位的坐标。保证 $x$ 或 $y$ 中至少有一个是整数，且小数位数不超过 $3$ 位。同时保证这 $k$ 个摊位的位置各不相同。

输出格式

输出一行一个实数，表示从入口出发，访问所有 $k$ 个摊位并到达出口所需的最短时间。如果你的输出与答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

样例

输入 1

3 3 6
1 2
3 4
5 6
1 2 3
4 5 6
0 0.5
0 1.5
0.5 1
1.5 2
2 0.1
2 0.9

输出 1

2.893333333

说明

对于样例，设 $S$ 为入口，$T$ 为出口。摊位按在样例中出现的顺序编号为 $A$ 到 $F$。下图展示了其中一条最短旅行时间的路线。

图中边旁边的数字表示沿该边移动的速度。