本题需要文件读写

文件 IO 为：输入文件 ticket.in，输出文件 ticket.out。请使用上述文件名读入和输出。

题目描述

游园路线依次设有 $Q$ 道检查站。小岚出发前有 $R$ 张红色通行券、$B$ 张蓝色通行券，以及足够的现金。

每道检查站都会给出两个方案，小岚必须从中选择一个，并按照所选方案付款后才能通过。这些方案共有三种类型：

• R：交出一张红色通行券。
• B：交出一张蓝色通行券。
• T-x：支付 $x$ 元现金。

同一道检查站给出的两个方案可以属于同一类型。例如，两个方案都是 R 时，通过该站仍然只需交出一张红券；两个方案都是现金付款时，也只需支付所选方案规定的金额。

通行券用掉后不会补充。当某种颜色的通行券已经用完时，就不能再选择需要该颜色通行券的方案。小岚只能选择检查站给出的方案，不能改用该站没有提供的付款方式。如果某一道检查站的两个方案都无法选择，小岚便无法通过整条路线。

小岚会按照检查站的排列顺序前进。不过，在出发前，她已经知道全部 $Q$ 道检查站的两个方案，因此可以提前安排每一站的选择。

请你求出，小岚通过全部检查站最少需要支付多少元现金。如果无法通过全部检查站，输出 -1。

输入格式

第一行包含一个整数 $T$，表示数据组数。各组数据互相独立。

对于每组数据：

• 第一行包含两个整数 $R, B$，分别表示初始红券和蓝券的数量。
• 第二行包含一个整数 $Q$，表示检查站的数量。
• 接下来 $Q$ 行，第 $i$ 行包含两个以空格分隔的字符串，表示第 $i$ 道检查站的两个方案。每个字符串都是 R、B 或 T-x 中的一种，其中 $x$ 为非负整数。

输出格式

对每组数据输出一行一个整数，表示通过全部检查站所需支付的最少现金金额。如果无法通过，输出 -1。

样例输入 1

1
1 3
4
R T-10
B R
B R
T-100 R

样例输出 1

10

说明

样例解释

小岚可以这样选择：

1. 第一站支付 $10$ 元现金。
2. 第二站交出一张蓝券。
3. 第三站交出一张蓝券。
4. 第四站交出一张红券。 总共支付 $10$ 元，使用一张红券、两张蓝券。

由于只有一张红券，第一站和第四站不可能都用红券通过，至少需要在其中一站支付现金。因此，支付 $10$ 元已经是最少的。

其它样例说明

• 样例 2：见选手目录下的 ticket/ticket2.in 与 ticket/ticket2.ans。该样例满足测试点 $1$ 的约束。
• 样例 3：见选手目录下的 ticket/ticket3.in 与 ticket/ticket3.ans。该样例满足测试点 $2 \sim 3$ 的约束。
• 样例 4：见选手目录下的 ticket/ticket4.in 与 ticket/ticket4.ans。该样例满足测试点 $4 \sim 6$ 的约束。
• 样例 5：见选手目录下的 ticket/ticket5.in 与 ticket/ticket5.ans。该样例满足测试点 $7 \sim 11$ 的约束。
• 样例 6：见选手目录下的 ticket/ticket6.in 与 ticket/ticket6.ans。该样例满足测试点 $12 \sim 15$ 的约束。
• 样例 7：见选手目录下的 ticket/ticket7.in 与 ticket/ticket7.ans。该样例满足测试点 $16 \sim 20$ 的约束。

数据范围

对于所有数据，保证 $1 \le T \le 20$。 每组数据满足 $0 \le R, B \le 10^5$，$1 \le Q \le 10^5$； 每个方案均为 R、B 或 T-x，其中 $0 \le x \le 10^4$。 同一输入文件内，所有组的 $Q$ 之和不超过 $2 \times 10^5$。

各测试点的附加约束如下表所示：

点击下载大样例