题目描述

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

::::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。

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
0
1

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
1
13
22

提示

【样例 #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{R}}$
$\mathtt{R}$	$\mathtt{X}$	$\orange{\mathtt{L}}$
$\mathtt{L}$		$\orange{\mathtt{R}}$
	$\mathtt{L}$

• 值得注意的一点是，对于方格 $(2,3)$，由于它总共经历了两次反转，所以仍然维持最开始的状态 $\mathtt{L}$。

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

Alice 总共需要花费 $a_2+b_3=2$ 枚金币，可以证明为最小花费。 :::

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

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

$\orange{\mathtt{L}}$	$\mathtt{L}$
$\orange{\mathtt{L}}$	$\mathtt{X}$	$\mathtt{L}$
$\orange{\mathtt{R}}$

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

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

:::

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

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

$\orange{\mathtt{L}}$	$\mathtt{L}$
$\orange{\mathtt{L}}$		$\mathtt{X}$		$\mathtt{L}$
$\mathtt{X}$	$\orange{\mathtt{R}}$
$\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{R}}$	$\mathtt{R}$					$\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}$		$\orange{\mathtt{L}}$		$\mathtt{L}$	$\mathtt{X}$		$\mathtt{L}$
$\mathtt{L}$		$\mathtt{X}$		$\orange{\mathtt{R}}$			$\mathtt{X}$		$\mathtt{X}$
		$\mathtt{L}$			$\mathtt{R}$	$\orange{\mathtt{L}}$
$\mathtt{X}$	$\mathtt{L}$	$\mathtt{R}$	$\mathtt{R}$	$\mathtt{X}$		$\mathtt{X}$	$\orange{\mathtt{R}}$	$\orange{\mathtt{R}}$	$\mathtt{L}$
$\mathtt{R}$		$\mathtt{X}$				$\mathtt{R}$	$\mathtt{X}$		$\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。