题目描述Description

赶集，也叫赶墟，趁墟，是一种历史悠久的民间传统贸易活动，指在特定日期和固定地点进行的商品交易与社交集会，具有鲜明的民俗特征和地域文化差异。

今天，你所在的城市正在进行一场端午大集，你打算前往其中的 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 个摊位之后到达出口所需要的最短时间。逛摊位所花时间忽略不计。

输入格式Input

第一行三个整数 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},\ldots,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},\ldots,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 个摊位的位置互不相同。

输出格式Output

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

样例Sample

提示Hint

对于样例，用 S 表示入口，T 表示出口，按在样例中出现的先后顺序给摊位编号为 A 到 F。一种花费时间最短的可行线路如下图所示。

边的旁边标注的数字为在这条边上移动的速度。

出题Author

来源Source