3008 - 象棋

小云和小南两姐妹从小喜欢下象棋，现在作为象棋高手的她们，已经不屑于玩平常的象棋了，于是她们便开始用棋 盘和棋子玩各种各样的新游戏。今天天气晴朗，阳光明媚，她们将在n * m的棋盘上进行游戏。棋盘上有k颗棋子和 若干有障碍格子，令棋盘左上角格子坐标为(1, 1)，右下角格子坐标为(n, m)，参数a、b规定了所有棋子的走法： 在(x, y)的棋子下一步能走到(x + a, y + b), (x + a, y - b), (x – a, y + b), (x – a, y – b), (x + b, y + a), (x + b, y - a), (x – b, y + a), (x – b, y – a)这八个格子中的一个，棋子任何时候不能跃出棋 盘或走到有障碍的格子上。这k颗棋子是相同的，小云和小南的目标是用最少步数把所有棋子移动到特定格子，要 求移动过程中不能出现多颗棋子同时在某一格的情况。她们已经想出步数较少方案，但无法确定这是否为最少步数 ，所以向作为程序员的你求助。

第一行五个空格隔开的整数n、m、k、a以及b； 接下来n行，每行为长度m的字符串，描述棋盘，‘.’表示没有障碍的格子，‘*’表示有障碍的格子； 接下来k行，每行两个整数x和y，分别表示k颗棋子的初始位置； 接下来k行，每行两个整数x和y，分别表示k颗棋子的目标位置。 n、m ≤ 100，k ≤ 500

一个整数，为把所有棋子移动到’t’位置的最少步数，数据保证有解。