The Beach

题目描述

有一个 n\times m 的网格图，场地上有许多不可移动的障碍，标记为 #，还有一些可以移动的障碍，如果他是横着的，定义它的一边为 L，另一边为 R；否则定义它的上边为 U，下边为 D，现在需要在这个网格图中空出一个 1\times 2 的空位，可以移动的障碍移动如下：

• 选择固定它的一边，将其旋转 90^\degree，花费 p 单位，前提是旋转后不准与其他障碍重合。
• 将其平移一个单位，花费 q 单位，前提是平移后不准与其他障碍重合。

现在要求出在这个网格图里空出 1\times 2 的空位，至少需要花费多少单位，如果不可能，输出 -1。

输入

第一行两个整数 1\leqslant n,m\leqslant 3\times 10^5,n\times m\leqslant 3\times 10^5，表示这个网格的大小。

第二行两个整数 1\leqslant p,q\leqslant 10^9，如题意所述。

接下来 n 行，每行 m 个字符，每个字符为 .（表示空位）、#（表示不可移动障碍）、L、R、U、D（分别表示可移动的障碍是如何摆放的）中的一种。

输出

输出一个整数表示最小花费，如果不存在这样的方案，输出 -1。

样例

提示

第一个样例中可以把位于 (1,2),(1,3) 的障碍往左移动一格，(2,3),(2,4) 的障碍往右移动一格，花费 2q=4。

第二个样例中无论如何移动障碍都不可能空出 1\times 2 的空位，输出 -1。