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,bi≤10^7)$，依次描述每张卡牌正面和背面的数字。

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

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

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