题目描述

Putata 正在他的笔记本电脑上玩一个著名的蛇形游戏，一条蛇在大小为𝑛×𝑚 的网格上移动。网格的某些单元格中可能有障碍物。蛇可以用一串坐标对来表示，这些坐标对决定了蛇身体的位置： (𝑥1,𝑦1),(𝑥2,𝑦2),…,(𝑥𝑘,𝑦𝑘) .其中， k𝑘 表示蛇的长度。蛇头位于 (𝑥1,𝑦1) ，蛇尾位于 (𝑥𝑘,𝑦𝑘) ，蛇身的相邻部分位于共用一条边的单元格中。

在这个游戏中，蛇被编程为一系列以字符串表示的命令。您可以使用 5 种命令：



	'L':命令小蛇向左移动一步。蛇头将移动到 (𝑥1,𝑦1−1) 。


	'R':命令蛇向右移动一步。蛇头将移动到 (𝑥1,𝑦1+1) 。


	'U':命令蛇向上移动一步。蛇头将移动到 (𝑥1−1,𝑦1) 。


	'D':命令蛇向下移动一步。蛇头将移动到 (𝑥1+1,𝑦1) 。


	'S':将蛇的长度缩短一步。蛇身的尾部将被删除。长度将变为 𝑘−1 。注意， 𝑘=1 时无法执行此操作。



当蛇头移动时，蛇身的各个部分也会相应移动。具体来说，身体的 𝑖部分( 2≤𝑖≤𝑘 )会移动到命令之前 (𝑖−1) /st部分所在的位置。蛇不能移动到有障碍物的单元格中，也不能移动到网格外。此外，蛇也不能与自己碰撞。所以你应该保证蛇身的任何两个部分都不会共用同一个位置。


考虑下面的角情况：蛇头位于 (𝑥1,𝑦1) ，蛇尾位于 (𝑥𝑘,𝑦𝑘) 。如果头部移动到 (𝑥1′,𝑦1′) ，那么就允许移动到 (𝑥1′,𝑦1′)=(𝑥𝑘,𝑦𝑘) ：如果我们考虑现实世界中的情况，头部移动到单元格时，尾部正好移动到单元格外。类似地，在 𝑘=2 时，使用一条命令就可以允许交换头部和尾部。


您将得到网格地图和蛇的身体序列。让 𝑓(𝑖,𝑗) 表示普塔塔至少需要使用多少条命令才能让蛇头到达 (𝑖,𝑗) ，如果不可能，则为 0 。你必须计算

输入格式

输入的第一行包含三个整数 𝑛 、 𝑚 和 𝑘 ( 1≤𝑛,𝑚≤3000 、 1≤𝑘≤min{𝑛𝑚,105} )，分别表示网格的大小和蛇的长度。

在接下来的 𝑘 行中，第 𝑖 行包含两个整数 𝑥𝑖 和 𝑦𝑖 ( 1≤𝑥𝑖≤𝑛 ， 1≤𝑦𝑖≤𝑚 ， 𝑥𝑖−𝑥𝑖+1|+|𝑦𝑖−𝑦𝑖+1|=1 )，表示蛇身第 𝑖 部分的位置。保证所有 𝑘 对 (𝑥𝑖,𝑦𝑖) 都是成对不同的。同时还保证每个部分都位于一个没有障碍物的单元格中。


在接下来的 𝑛 行中，第 i𝑖 行包含一个长度为 𝑚 的字符串。如果单元格 (𝑖,𝑗) 为空，那么在这些行的 𝑖 中的 𝑗 字符是'.'。如果单元格 (𝑖,𝑗) 中有障碍物，则该字符为 "#"。

输出格式

打印一行，其中包含一个整数：问题答案。

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

293