安德鲁喜欢大海。这就是为什么在盛夏时节,他决定去海滩,带着日光浴床享受日光浴。
海滩是一个矩形区域,有 $$$n$$$ 行和 $$$m$$$ 列。海滩的一些单元是免费的,有些有道路、石头、商店和其他不可移动的物体。沿侧边相邻的两个单元中的一些可以具有水平或垂直放置的日光浴床。
安德鲁希望把他的日光浴床放在某个地方,但运气不好,可能不再有空闲的地方了!这就是为什么安德鲁要求你帮助他找到一个免费的地方来放置他的日光浴床。安德鲁的日光浴床也应该放置在两个相邻的牢房上。
如果没有两个相邻的空闲单元,那么为了腾出一些地方放置日光浴床,您将不得不打扰其他游客。您可以执行以下操作:
- 来到日光浴床前,在给主人造成 $$$p$$$ 单位的不适后,抬起日光浴床的一侧并将其旋转 $$$90$$$ 度。日光浴床的一半必须保留在同一牢房中,另一半必须移至空闲牢房。与此同时,在旋转过程中,任何东西都可能出现在日光浴床的路上。 日光浴床围绕单元 $$$(1, 2)$$$ 旋转 $$$90$$$ 度。
- 来到某个日光浴床前,在对其主人造成 $$$q$$$ 单位的不适后,将日光浴床沿其长边移动一个格子。日光浴床的一半必须移至另一半的位置,另一半则移至空闲牢房。 日光浴床向右移动一格。
在任何时刻,每个日光浴床都会占据两个相邻的空闲单元。您一次不能移动超过一张日光浴床。
帮助安德鲁为他的日光浴床腾出空间,尽可能减少对其他游客造成的不适,或者发现这是不可能的。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 300\,000$$$, $$$1 \le n \cdot m \le 300\,000$$$) — 矩形中的行数和列数。
第二行包含两个整数 $$$p$$$ 和 $$$q$$$ ($$$1 \le p, q \le 10^9$$$) - 分别是由日光浴床的旋转和移动引起的不适的单位数。
以下 $$$n$$$ 行均包含 $$$m$$$ 个字符,描述矩形的单元格。每行由字符“L”、“R”、“D”、“U”、“.”组成。和“#”,表示单元格的类型。字符“L”、“R”、“D”和“U”表示放置在牢房中的日光浴床的一半——分别是左半部、右半部、下半部和上半部。特点 ”。”表示一个空闲单元格和字符“#”——一个单元格,被一些不可移动的物体占据。
输出
打印一个整数 - 为释放日光浴床空间而对其他游客造成的不适的最小可能单位数。如果无法腾出空间放置日光浴床,请打印 $$$-1$$$。
示例
输入 #1
2 5 5 2 .LR## ##LR.
输出 #1
4
输入 #2
2 3 4 5 LR. #.#
输出 #2
-1
输入 #3
4 3 10 10 .LR ### UU# DD.
输出 #3
-1
输入#4
3 6 10 7 .U##.# #DLR## .##LR.
输出#4
24
注意
在第一个示例中,我们可以将上部日光浴床移至左侧,将下部日光浴床移至右侧。安德鲁将能够将他的日光浴床垂直放置在海滩中央。我们很可能会造成 $$$2 + 2 = 4$$$ 单位的不适。很容易证明它是最优答案。
第一个示例中的最佳策略(安德鲁的日光浴床是白色的)。