网格路径的并集

时间限制：2s
空间限制：512MB

题目描述

有一个 $H\times W$ 的网格，从上往下第 $h$ 行、从左往右第 $w$ 列的格子记为 $(h,w)$。另给定一个长度为 $H+W-2$ 的字符串 $S=S_1S_2\cdots S_{H+W-2}$，其中每个字符都是 D、R 或 ?。

初始时所有格子均为白色。你可以进行任意多次操作，每次操作依次执行以下步骤：

1. 选择一个长度为 $H+W-2$ 的字符串 $X=X_1X_2\cdots X_{H+W-2}$。其中恰有 $H-1$ 个 D 和 $W-1$ 个 R；若 $S_i$ 为 D 或 R，则必须有 $X_i=S_i$。
2. 从格子 $(1,1)$ 出发，按顺序执行 $X$ 中的移动：D 表示向下移动一格，R 表示向右移动一格。满足条件的 $X$ 一定不会使你走出网格。
3. 将本次经过的所有格子（包括起点和终点）染成黑色；已经是黑色的格子保持不变。

求最终最多能染黑多少个格子。

有 $T$ 组测试数据，请分别求解。

输入格式

第一行一个整数 $T$，表示测试数据组数。

接下来每组测试数据包含两行：第一行两个整数 $H,W$，第二行一个字符串 $S$。

输出格式

输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

样例输入 1

4
4 5
D?DRR?R
4 5
DDRRDRR
4 5
???????
2 2
DR

样例输出 1

12
8
20
3

样例说明 1

对于第一组测试数据，第一次令 $X=$ DRDRRDR，第二次令 $X=$ DDDRRRR，可以将 $12$ 个格子染成黑色。下图分别展示这两条路径。

数据范围

• $1\le T\le 2\times 10^5$；
• $2\le H,W\le 2\times 10^5$；
• $S$ 的长度为 $H+W-2$，且只包含 D、R、?；
• $S$ 中 D 的数量不超过 $H-1$，R 的数量不超过 $W-1$；
• 所有测试数据中 $\sum(H+W)\le 4\times 10^5$。