题目描述

Alice有 $n$ 张卡牌，第 $i$ ($1≤i≤n$) 张卡牌的正面有数字 $a_i$，背面有数字 $b_i$，初始时所有卡牌正面朝上。

现在Alice可以将任意张（包括 $0$ 张或者全部 $n$ 张）卡牌翻面，即由正面朝上改为背面朝上。这 $n$ 张卡牌是有魔法的，Alice必须遵守全部 $m$ 条规则，每条规则是下面两种之一：

• A x y ($1≤x,y≤n, x≠y$): 仅考虑最终的局面而不考虑过程，如果最终第 $x$ 张卡牌正面向上，那么最终第 $y$ 张卡牌必须背面向上。
• B x y ($1≤x,y≤n, x≠y$): 仅考虑最终的局面而不考虑过程，如果最终第 $x$ 张卡牌正面向上，那么最终第 $y$ 张卡牌必须正面向上。

Alice的目标是让最终朝上的 $n$ 个数字的总和尽量大。请你帮Alice算一算总和的最大值是多少。

输入格式

第一行包含一个正整数 $T$ ($1≤T≤300$)，表示测试数据的组数。

每组数据第一行包含两个正整数 $n,m$ ($2≤n≤60, 1≤m≤5000$)，分别表示卡牌和规则的数量。

接下来 $n$ 行，每行两个整数 $a_i,b_i$ ($0≤a_i,b_i≤10^7$)，依次描述每张卡牌正面和背面的数字。

接下来 $m$ 行，每行描述一条规则。

输入数据保证最多只有 $10$ 组数据满足 $n>30$。

输出格式

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

输入样例

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

输出样例

9 1