魔法卡牌

Problem Description

Alice有 $n$ 张卡牌，第 $i$ ($1\leq i\leq n$) 张卡牌的正面有数字 $a_i$，背面有数字 $b_i$，初始时所有卡牌正面朝上。 现在Alice可以将任意张（包括 $0$ 张或者全部 $n$ 张）卡牌翻面，即由正面朝上改为背面朝上。这 $n$ 张卡牌是有魔法的，Alice必须遵守全部 $m$ 条规则，每条规则是下面两种之一：

• ''$\texttt{A x y}$'' ($1\leq x,y\leq n$, $x\neq y$): 仅考虑最终的局面而不考虑过程，如果最终第 $x$ 张卡牌正面向上，那么最终第 $y$ 张卡牌必须背面向上。
• ''$\texttt{B x y}$'' ($1\leq x,y\leq n$, $x\neq y$): 仅考虑最终的局面而不考虑过程，如果最终第 $x$ 张卡牌正面向上，那么最终第 $y$ 张卡牌必须正面向上。 Alice的目标是让最终朝上的 $n$ 个数字的总和尽量大。请你帮Alice算一算总和的最大值是多少。

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 300$)，表示测试数据的组数。 每组数据第一行包含两个正整数 $n,m$ ($2\leq n\leq 60$, $1\leq m\leq 5000$)，分别表示卡牌和规则的数量。 接下来 $n$ 行，每行两个整数 $a_i,b_i$ ($0\leq a_i,b_i\leq 10^7$)，依次描述每张卡牌正面和背面的数字。 接下来 $m$ 行，每行描述一条规则。 输入数据保证最多只有 $10$ 组数据满足 $n > 30$。

Output

对于每组数据输出一行两个整数：最终朝上的 $n$ 个数字的总和的最大值以及对应的方案数。两个方案被认为不同当且仅当存在一张卡牌在一个方案中正面朝上，并在另一个方案中背面朝上。由于一定可以将所有卡牌背面朝上，因此一定存在合法方案。

Sample Input

1
3 2
5 3
1 3
3 1
A 1 3
B 1 2

Sample Output

9 1

Source

2024“钉耙编程”中国大学生算法设计超级联赛（4）