#213621. 【MGVOI R1-C】收集括号（brackets）

本题中 合法括号串 的定义如下：

::::info[合法括号串的定义]{open}

• () 是合法括号串。
• 若 A 是合法括号串，则 (A) 也是合法括号串。
• 若 A，B 均为合法括号串，则 AB 也是合法括号串。
• 所有的合法括号串都可以通过上述三条规则得到。

::::

Alice 和 Bob 正在合作玩一款叫做“收集括号”的游戏！这个游戏总共分为以下三步流程：

::::success[第一步：初始化]{open}

• 首先，计算机会自动生成一个 行 列的方格图，其中第 行第 列的方格对应的坐标为 。例如，左上角方格的坐标为 ，右下角方格的坐标为 。

• 然后，计算机会在每个方格中都填入一个字符（从 L，R，X 中选择）。若某个方格中的字符为 L，则表示方格中有一个左括号；若为 R，则表示方格中有一个右括号；若为 X，则表示方格中有一个障碍物。

::::

::::success[第二步：Alice 的行动回合]{open}

• 在第一步流程完全结束之后，Alice 可以对方格图进行任意次（包括 次）反转操作。

• 在一次反转操作中，Alice 首先需要选择方格图的 某一行或某一列 作为这次操作的范围。

• 之后，计算机将遍历 Alice 选择的这一行（或这一列）。对于每一个范围内的方格（除了障碍物），计算机都会反转这个方格上的字符。也就是说，如果方格上原先的字符是 L，那么就将其改为 R；如果原先是 R，那么就将其改为 L；如果原先是 X，那么不做任何改动。

• 对于这一次反转操作而言，如果 Alice 选择了第 行（）作为反转范围，那么需要花费 枚金币；如果她选择了第 列（）作为反转范围，那么需要花费 枚金币。

::::

::::success[第三步：Bob 的行动回合]{open}

• 在第二步流程完全结束之后，Bob 将从坐标为 的方格处（也就是方格图的左上角）出发，开始收集方格图中的括号。

• 在任意时刻，Bob 都可以选择 向正下方或正右方 移动一个方格（前提是要到达的位置既不超过方格图的边界，也没有障碍物）。也就是说，如果 Bob 位于方格 ，那么他下一步就可以前往方格 或者方格 ，只要他保证自己 始终位于方格图的范围内，并且不会前往有障碍物的方格。

• Bob 每到达一个方格，就会收集这个方格中的括号。在抵达坐标为 的终点方格（也就是方格图的右下角）之后，他会整理自己收集到的所有括号（包括起点和终点方格的括号），并将其 由先到后按照收集的顺序 排成一个字符串 。

• 如果 是一个合法括号串，则 Alice 和 Bob 在这局游戏中共同获胜；否则他们在这局游戏中落败。（如果 Bob 无法到达终点方格，则也认为他们落败） ::::

注意： 我们假设 Bob 是绝顶聪明的，也就是说，在 Alice 的所有操作完成之后，只要存在任何一种符合上述规则的行动方式能让他们获胜，Bob 就会采用这种行动方式。

在计算机已经填满方格图的情况下（即第一步的初始化流程已经完成），请你帮 Alice 判断，是否存在一种操作方案，使得她能够和 Bob 共同获胜？如果存在，则她最少需要花费多少枚金币来取胜？

每个测试点包含多组测试数据，各组测试数据之间相互独立。

第一行包含一个正整数 ，表示测试数据的组数。

对于每组测试数据：

第一行包含两个正整数 ，分别表示方格图的行数和列数。保证 是一个奇数，这意味着 Bob 最终得到的字符串 的长度一定为偶数。

第二行包含 个正整数，其中第 个正整数 表示在方格图的第 行进行反转操作需花费的金币数量。

第三行包含 个正整数，其中第 个正整数 表示在方格图的第 列进行反转操作需花费的金币数量。

接下来 行，每行包含一个长度为 的字符串（仅含 L，R，X 三种字符），其中第 行第 个字符即为计算机在方格 中填入的字符。保证左上角和右下角方格中的字符不为 X。

对于每组测试数据，仅需在单独一行输出一个整数：

• 如果 Alice 有可能和 Bob 共同获胜，则输出她最少需要花费的金币数；

• 否则，输出 -1。

样例输入 1

3
1 4
1
1 1 1 1
LXXR
1 4
1
1 1 1 1
LLRR
2 3
1 1
1 1 1
LRR
XRL

样例输出 1

-1
0
1

样例输入 2

4
4 3
1 1 1 9
1 1 1
LLL
LXL
LXL
LLL
4 3
1 1 1 1
1 1 1
LLL
LXL
LXL
LLL
4 5
8 5 6 3
8 5 6 5 3
RRRRR
RRXXR
XRRRL
RXLLR
7 10
10 100 1 1 100 1 10
10 1 1 1 1 1 1 1 1 10
RLLLLLLLXX
RXLXLXLLRL
RLLLLLXLLL
LLXXRRRXLX
LLLLLRLLLX
XLLLXLXLLR
LLXLXLLXLL

样例输出 2

2
1
13
22

【样例 #1】

::::info[样例 #1 解释]

对于第一组测试数据，计算机生成的方格图为 LXXR。由于中间两个障碍物的阻挡，Bob 无法从方格 向右移动到方格 ，故 Alice 和 Bob 不可能获胜，输出 -1；

对于第二组测试数据，计算机生成的方格图为 LLRR。显然，Bob 可以直接从方格 向右移动到方格 ，最终得到的 就是一个合法括号串。因此，Alice 无需花费任何金币进行反转操作即可获胜，输出 0；

对于第三组测试数据，Alice 只需花费 枚金币对第三列使用一次反转操作。在这之后，方格图的状态变为：

Bob 只需按照橙色方格对应的路径行动，最终可以得到 ，这是一个合法括号串。

容易证明，要让他们获胜最少需要 枚金币，故输出 1。

::::

【样例 #2】

::::info[样例 #2 解释]

:::success[第一组测试数据]

对于第一组测试数据，Alice 可以分别对第二行和第三列使用反转操作。在这之后，方格图的状态变为：

• 值得注意的一点是，对于方格 ，由于它总共经历了两次反转，所以仍然维持最开始的状态 。

Bob 只需按照橙色方格对应的路径行动，最终可以得到 ，这是一个合法括号串。

Alice 总共需要花费 枚金币，可以证明为最小花费。 :::

:::success[第二组测试数据]

对于第二组测试数据，Alice 可以对第四行使用反转操作。在这之后，方格图的状态变为：

Bob 只需按照橙色方格对应的路径行动，最终可以得到 ，这是一个合法括号串。

Alice 总共需要花费 枚金币，可以证明为最小花费。

:::

:::success[第三组测试数据]

对于第三组测试数据，Alice 可以分别对第一行、第二行使用反转操作。在这之后，方格图的状态变为：

Bob 只需按照橙色方格对应的路径行动，最终可以得到 ，这是一个合法括号串。

Alice 总共需要花费 枚金币，可以证明为最小花费。

:::

:::success[第四组测试数据]

对于第四组测试数据，Alice 可以分别对第一行、第六行、第七行、第二列使用反转操作。在这之后，方格图的状态变为：

Bob 只需按照橙色方格对应的路径行动，最终可以得到 ，这是一个合法括号串。（注：括号串的颜色仅为方便观察，与答案无关）

Alice 总共需要花费 枚金币，可以证明为最小花费。 :::

::::

【样例 #3】

见附件中的 brackets/brackets3.in 与 brackets/brackets3.ans。

这个样例满足测试点 的限制。

【样例 #4】

见附件中的 brackets/brackets4.in 与 brackets/brackets4.ans。

这个样例满足测试点 的限制。

【样例 #5】

见附件中的 brackets/brackets5.in 与 brackets/brackets5.ans。

这个样例满足测试点 的限制。

【数据范围】

对于所有测试点，保证 ，（ 为奇数），，并且方格图中初始填入的字符仅含 L，R，X，其中左上角和右下角的字符一定不为 X。

::cute-table{tuack}

特殊性质 A：保证 。

• 分值分配：每个测试点的分值为 分。
• 为避免对算法复杂度常系数的考察，本题的时间限制被设为 1.5s。