P13731 【MGVOI R1-C】收集括号（brackets）
题目描述
本题中 **合法括号串** 的定义如下：
::::info[合法括号串的定义]{open}
* ```()``` 是合法括号串。
* 若 ```A``` 是合法括号串，则 ```(A)``` 也是合法括号串。
* 若 ```A```，```B``` 均为合法括号串，则 ```AB``` 也是合法括号串。
* 所有的合法括号串都可以通过上述三条规则得到。
::::
Alice 和 Bob 正在合作玩一款叫做“收集括号”的游戏！这个游戏总共分为以下三步流程：
::::success[第一步：初始化]{open}
* 首先，计算机会自动生成一个 $n$ 行 $m$ 列的方格图，其中第 $i$ 行第 $j$ 列的方格对应的坐标为 $(i,j)$。例如，左上角方格的坐标为 $(1,1)$，右下角方格的坐标为 $(n,m)$。
* 然后，计算机会在每个方格中都填入一个字符（从 ```L```，```R```，```X``` 中选择）。若某个方格中的字符为 ```L```，则表示方格中有一个左括号；若为 ```R```，则表示方格中有一个右括号；若为 ```X```，则表示方格中有一个障碍物。
::::
::::success[第二步：Alice 的行动回合]{open}
* **在第一步流程完全结束之后**，Alice 可以对方格图进行任意次（包括 $0$ 次）**反转操作**。
* 在一次反转操作中，Alice 首先需要选择方格图的 **某一行或某一列** 作为这次操作的范围。
* 之后，计算机将遍历 Alice 选择的这一行（或这一列）。对于每一个范围内的方格（除了障碍物），计算机都会反转这个方格上的字符。也就是说，如果方格上原先的字符是 ```L```，那么就将其改为 ```R```；如果原先是 ```R```，那么就将其改为 ```L```；如果原先是 ```X```，那么不做任何改动。
* 对于这一次反转操作而言，如果 Alice 选择了第 $i$ 行（$1\le i\le n$）作为反转范围，那么需要花费 $a_i$ 枚金币；如果她选择了第 $j$ 列（$1\le j\le m$）作为反转范围，那么需要花费 $b_j$ 枚金币。
::::
::::success[第三步：Bob 的行动回合]{open}
* **在第二步流程完全结束之后**，Bob 将从坐标为 $(1,1)$ 的方格处（也就是方格图的左上角）出发，开始收集方格图中的括号。
* 在任意时刻，Bob 都可以选择 **向正下方或正右方** 移动一个方格（前提是要到达的位置既不超过方格图的边界，也没有障碍物）。也就是说，如果 Bob 位于方格 $(x,y)$，那么他下一步就可以前往方格 $(x+1,y)$ 或者方格 $(x,y+1)$，只要他保证自己 **始终位于方格图的范围内，并且不会前往有障碍物的方格**。
* Bob 每到达一个方格，就会收集这个方格中的括号。在抵达坐标为 $(n,m)$ 的终点方格（也就是方格图的右下角）之后，他会整理自己收集到的所有括号（包括起点和终点方格的括号），并将其 **由先到后按照收集的顺序** 排成一个字符串 $S$。
* 如果 $S$ 是一个合法括号串，则 Alice 和 Bob 在这局游戏中共同获胜；否则他们在这局游戏中落败。（如果 Bob 无法到达终点方格，则也认为他们落败）
::::
---
**注意：** 我们假设 Bob 是绝顶聪明的，也就是说，在 Alice 的所有操作完成之后，只要存在任何一种符合上述规则的行动方式能让他们获胜，Bob 就会采用这种行动方式。
在计算机已经填满方格图的情况下（即第一步的初始化流程已经完成），请你帮 Alice 判断，是否存在一种操作方案，使得她能够和 Bob 共同获胜？如果存在，则她最少需要花费多少枚金币来取胜？
输入格式
**每个测试点包含多组测试数据，各组测试数据之间相互独立。**
第一行包含一个正整数 $T$，表示测试数据的组数。
对于每组测试数据：
第一行包含两个正整数 $n,m$，分别表示方格图的行数和列数。**保证 $\bm{n+m}$ 是一个奇数**，这意味着 Bob 最终得到的字符串 $S$ 的长度一定为偶数。
第二行包含 $n$ 个正整数，其中第 $i$ 个正整数 $a_i$ 表示在方格图的第 $i$ 行进行反转操作需花费的金币数量。
第三行包含 $m$ 个正整数，其中第 $j$ 个正整数 $b_j$ 表示在方格图的第 $j$ 列进行反转操作需花费的金币数量。
接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串（仅含 ```L```，```R```，```X``` 三种字符），其中第 $i$ 行第 $j$ 个字符即为计算机在方格 $(i,j)$ 中填入的字符。保证左上角和右下角方格中的字符不为 ```X```。
输出格式
对于每组测试数据，仅需在单独一行输出一个整数：
* 如果 Alice 有可能和 Bob 共同获胜，则输出她最少需要花费的金币数；
* 否则，输出 ```-1```。
说明/提示
**【样例 #1】**
::::info[样例 #1 解释]
对于第一组测试数据，计算机生成的方格图为 ```LXXR```。由于中间两个障碍物的阻挡，Bob 无法从方格 $(1,1)$ 向右移动到方格 $(1,4)$，故 Alice 和 Bob 不可能获胜，输出 ```-1```；
对于第二组测试数据，计算机生成的方格图为 ```LLRR```。显然，Bob 可以直接从方格 $(1,1)$ 向右移动到方格 $(1,4)$，最终得到的 $S=(())$ 就是一个合法括号串。因此，Alice 无需花费任何金币进行反转操作即可获胜，输出 ```0```；
对于第三组测试数据，Alice 只需花费 $b_3=1$ 枚金币对第三列使用一次反转操作。在这之后，方格图的状态变为：
| $\orange{\mathtt{L}}$ | $\orange{\mathtt{R}}$ | $\orange{\mathtt{L}}$ |
| -----------: | -----------: | -----------: |
| $\mathtt{X}$ | $\mathtt{R}$ | $\orange{\mathtt{R}}$ |
Bob 只需按照橙色方格对应的路径行动，最终可以得到 $S=()()$，这是一个合法括号串。
容易证明，要让他们获胜最少需要 $1$ 枚金币，故输出 ```1```。
::::
**【样例 #2】**
::::info[样例 #2 解释]
:::success[第一组测试数据]
对于第一组测试数据，Alice 可以分别对第二行和第三列使用反转操作。在这之后，方格图的状态变为：
| $\orange{\mathtt{L}}$ | $\orange{\mathtt{L}}$ | $\orange{\mathtt{R}}$ |
| -----------: | -----------: | -----------: |
| $\mathtt{R}$ | $\mathtt{X}$ | $\orange{\mathtt{L}}$ |
| $\mathtt{L}$ | $\mathtt{X}$ | $\orange{\mathtt{R}}$ |
| $\mathtt{L}$ | $\mathtt{L}$ | $\orange{\mathtt{R}}$ |
* 值得注意的一点是，对于方格 $(2,3)$，由于它总共经历了两次反转，所以仍然维持最开始的状态 $\mathtt{L}$。
Bob 只需按照橙色方格对应的路径行动，最终可以得到 $S=(()())$，这是一个合法括号串。
Alice 总共需要花费 $a_2+b_3=2$ 枚金币，可以证明为最小花费。
:::
:::success[第二组测试数据]
对于第二组测试数据，Alice 可以对第四行使用反转操作。在这之后，方格图的状态变为：
| $\orange{\mathtt{L}}$ | $\mathtt{L}$ | $\mathtt{L}$ |
| -----------: | -----------: | -----------: |
| $\orange{\mathtt{L}}$ | $\mathtt{X}$ | $\mathtt{L}$ |
| $\orange{\mathtt{L}}$ | $\mathtt{X}$ | $\mathtt{L}$ |
| $\orange{\mathtt{R}}$ | $\orange{\mathtt{R}}$ | $\orange{\mathtt{R}}$ |
Bob 只需按照橙色方格对应的路径行动，最终可以得到 $S=((()))$，这是一个合法括号串。
Alice 总共需要花费 $a_4=1$ 枚金币，可以证明为最小花费。
:::
:::success[第三组测试数据]
对于第三组测试数据，Alice 可以分别对第一行、第二行使用反转操作。在这之后，方格图的状态变为：
| $\orange{\mathtt{L}}$ | $\mathtt{L}$ | $\mathtt{L}$ | $\mathtt{L}$ | $\mathtt{L}$ |
| -----------: | -----------: | -----------: | -----------: | -----------: |
| $\orange{\mathtt{L}}$ | $\orange{\mathtt{L}}$ | $\mathtt{X}$ | $\mathtt{X}$ | $\mathtt{L}$ |
| $\mathtt{X}$ | $\orange{\mathtt{R}}$ | $\orange{\mathtt{R}}$ | $\orange{\mathtt{R}}$ | $\mathtt{L}$ |
| $\mathtt{R}$ | $\mathtt{X}$ | $\mathtt{L}$ | $\orange{\mathtt{L}}$ | $\orange{\mathtt{R}}$ |
Bob 只需按照橙色方格对应的路径行动，最终可以得到 $S=((()))()$，这是一个合法括号串。
Alice 总共需要花费 $a_1+a_2=13$ 枚金币，可以证明为最小花费。
:::
:::success[第四组测试数据]
对于第四组测试数据，Alice 可以分别对第一行、第六行、第七行、第二列使用反转操作。在这之后，方格图的状态变为：
| $\orange{\mathtt{L}}$ | $\orange{\mathtt{L}}$ | $\orange{\mathtt{R}}$ | $\mathtt{R}$ | $\mathtt{R}$ | $\mathtt{R}$ | $\mathtt{R}$ | $\mathtt{R}$ | $\mathtt{X}$ | $\mathtt{X}$ |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
| $\mathtt{R}$ | $\mathtt{X}$ | $\orange{\mathtt{L}}$ | $\mathtt{X}$ | $\mathtt{L}$ | $\mathtt{X}$ | $\mathtt{L}$ | $\mathtt{L}$ | $\mathtt{R}$ | $\mathtt{L}$ |
| $\mathtt{R}$ | $\mathtt{R}$ | $\orange{\mathtt{L}}$ | $\orange{\mathtt{L}}$ | $\orange{\mathtt{L}}$ | $\mathtt{L}$ | $\mathtt{X}$ | $\mathtt{L}$ | $\mathtt{L}$ | $\mathtt{L}$ |
| $\mathtt{L}$ | $\mathtt{R}$ | $\mathtt{X}$ | $\mathtt{X}$ | $\orange{\mathtt{R}}$ | $\orange{\mathtt{R}}$ | $\orange{\mathtt{R}}$ | $\mathtt{X}$ | $\mathtt{L}$ | $\mathtt{X}$ |
| $\mathtt{L}$ | $\mathtt{R}$ | $\mathtt{L}$ | $\mathtt{L}$ | $\mathtt{L}$ | $\mathtt{R}$ | $\orange{\mathtt{L}}$ | $\orange{\mathtt{L}}$ | $\mathtt{L}$ | $\mathtt{X}$ |
| $\mathtt{X}$ | $\mathtt{L}$ | $\mathtt{R}$ | $\mathtt{R}$ | $\mathtt{X}$ | $\mathtt{R}$ | $\mathtt{X}$ | $\orange{\mathtt{R}}$ | $\orange{\mathtt{R}}$ | $\mathtt{L}$ |
| $\mathtt{R}$ | $\mathtt{L}$ | $\mathtt{X}$ | $\mathtt{R}$ | $\mathtt{X}$ | $\mathtt{R}$ | $\mathtt{R}$ | $\mathtt{X}$ | $\orange{\mathtt{R}}$ | $\orange{\mathtt{R}}$ |
Bob 只需按照橙色方格对应的路径行动，最终可以得到 $S=(\red{()}\blue{(}\red{((()))}\orange{(())}\blue{)})$，这是一个合法括号串。（注：括号串的颜色仅为方便观察，与答案无关）
Alice 总共需要花费 $a_1+a_6+a_7+b_2=22$ 枚金币，可以证明为最小花费。
:::
::::
**【样例 #3】**
见附件中的 ```brackets/brackets3.in``` 与 ```brackets/brackets3.ans```。
这个样例满足测试点 $5 \sim 8$ 的限制。
**【样例 #4】**
见附件中的 ```brackets/brackets4.in``` 与 ```brackets/brackets4.ans```。
这个样例满足测试点 $9 \sim 12$ 的限制。
**【样例 #5】**
见附件中的 ```brackets/brackets5.in``` 与 ```brackets/brackets5.ans```。
这个样例满足测试点 $13 \sim 20$ 的限制。
---
**【数据范围】**
对于所有测试点，保证 $1\le T\le 5$，$1\le n,m\le 100$（$n+m$ 为奇数），$1\le a_i,b_j\le 10^5$，并且方格图中初始填入的字符仅含 ```L```，```R```，```X```，其中左上角和右下角的字符一定不为 ```X```。
::cute-table{tuack}
| **测试点编号** | $T \le$ | $n,m \le$ | $n+m\le$ | **特殊性质** |
|:-:|:-:|:-:|:-:|:-:|
| $1 \sim 4$ | $1$ | $6$ | $7$ | 无
| $5 \sim 8$ | $2$ | $14$ | $15$ | ^
| $9 \sim 12$ | $5$ | $100$ | $101$ | **A**
| $13 \sim 20$ | ^ | ^ | $199$ | 无
特殊性质 **A**：保证 $n=1$。
* 分值分配：每个测试点的分值为 $5$ 分。
* 为避免对算法复杂度常系数的考察，本题的时间限制被设为 1.5s。