组合扑克

题目描述

我们都知道，一副扑克牌共有54张不同花色以及点数的牌型各一张，其中包括2张王牌，4种不同的花色13种不同的点数共52张。花色分别是方片,黑桃,草花以及红桃，点数从A，2，3 ... 10,J,Q,K构成。特别的，其中A表示 $1$，J Q K分别表示 $11,12,13$。

特别的，在大部分扑克牌游戏中，点数 3 一般被认为是最小的牌，而点数 2 和 A 被认为大于 K。完整的点数大小排序应该为：3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A < 2 < 黑王 < 红王。

同时，在部分扑克牌游戏中，我们对于牌型也会有若干不同的组合，即可以将多张不同的牌一次打出，我们这里主要讨论如下几种牌型：

• 单张牌：即不进行任何组合，直接将单张牌打出。
• 对子：将两张点数相同的牌组合打出（不考虑花色）。
• 飞机：将三张点数相同的牌组合打出（不考虑花色）。
• 顺子：将五张点数升序且连续的牌组合打出（不考虑花色），例如 3 4 5 6 7。特别的，这里的点数升序指的是牌面的点数大小升序，即按照上述的点数大小排序的规则升序，但是 2 和 红王 以及 黑王 不能成为顺子的一部分，即 10 J Q K A 是合法的顺子，而 J Q K A 2 不是，因为 2 不能成为顺子的一部分。

现在，我们将拓展扑克牌的玩法，我们对传统扑克牌玩法做出如下改动：

• 将点数从原来的$1$ 到 $13(K)$ 修改成 $1$ 到 $n$，即共有 $n$ 种不同的点数，这意味着一副扑克牌可能会有 $4 \times n + 2$ 种不同的牌型，即四种花色的所有点数各一种和红黑王。
• 去掉原来每种牌型只能有一张的限制，即现在一副扑克牌最多存在 $m$ 张牌，相同的牌型可能会有多张。
• 对于对子和飞机，他们同样对王牌生效，即 黑王 黑王 是一个合法的对子，但 黑王 红王 不是，因为他们的点数不同。
• 对于顺子做出如下限制:
• • 2 可以作为比 3 小的点数成为顺子的一部分，例如 2 3 4 5 6 是合法的顺子，但 2 任然不可以作为 A 的下一位成为顺子，即 J Q K A 2 任然不是合法的顺子。
• • A 不仅可以作为点数 $n$ 的下一位作为顺子，亦可作为上一条规则中比 2 小的点数成为顺子的一部分，例如 A 2 3 4 5 和 10 J Q K A(假设 $n = 13$)都是合法的顺子。
• • 对于点数大小的排序任然遵循 3 < 4 < 5 < ... < n - 2 < n - 1 < n < A < 2 < 黑王 < 红王。这条规则表示，2 和 A 在上述顺子中仅仅具有可以和其他点数结合成顺子的性质，而其本身点数的大小并不会改变。

现在，我们会给定你 $n$，以及 $T$ 组不同的牌型，保证每组牌型不超过 $m$ 张牌，你需要利用上述性质尽可能的将给出的牌凑出上述的组合牌型(即对子，飞机和顺子)，使得剩余的单张牌尽可能地少。你最后需要给出，剩余的单张牌中，点数大小小于 A 的单张牌的数量。换句话说，你应该利用上述牌型对组合你的手牌，最小化小于点数A的牌型的单张牌组合的数量。

输入格式

输入一行，包含2个整数 $n$ 和 $T$，$n$ 表示点数种类数量，$T$ 表示测试数据组数。 对于每组测试数据，输入包含 $1$ 行，为一个字符串 $S$，其遵循如下格式：

花色 点数 花色 点数 花色 点数 花色 点数...

其中一张牌的信息包含两部分，即花色和点数，他们由一个空格隔开。同时，不同牌型的信息同样用一个空格隔开。数据保证每行字符串都一定是 花色 点数 这样的组合，不存在非法数据。

对于输入的花色，其中D表示方片，C 表示草花，H表示红桃，S表示黑桃。对于输入的点数，我们的输入数据将直接用数字来表示，即传统扑克中J Q K 这样的牌型这样会统一用 11 12 13来表示，但点数 A 任然会用 A 来表示。特别的，如果牌型是王牌，我们会用花色B来表示黑王，R来表示红王，且保证王牌后的点数一定是0。

数据范围

对于 $30\%$ 的数据，$n \le 15$，$1 \le m \le 50$。 对于 $50\%$ 的数据，$n \le 20$，$1 \le m \le 100$。 对于 $70\%$ 的数据，$n \le 100$，$1 \le m \le 500$。 对于 $100\%$ 的数据，$n \le 500$，$1 \le m \le 2000$，$1 \le T \le 100$。

注意，数据范围中的 $m$ 仅作为对于每组测试数据中扑克数量的限制，并不会在输入中给出。

输出格式

对于每组测试数据，输出一行，其中包含一个整数表示答案。

样例 #1

样例输入 #1

13 3
S A D 2 C 3 H 4 D 5 S 6
D A D A C 2 C 2 H 3 H 3 S 4 D 5 C 5
B 0 R 0 H A C 3

样例输出 #1

0
1
1

提示

样例解释1：

输入的牌包含SA，D2，C3，H4，D5和H6，最优的组牌方案应该是将D2，C3，H4，D5和H6组成顺子，将SA作为单张，此时比点数A小的单张牌组合的数量为0，可以证明这是最优的组合方案。