SP3111 STABARDS - Stabards

在遥远的星系中，生活着一种硅基生命体，称为 stabards。与人类不同，stabards 拥有多个性别。当两个 stabards 形成伴侣关系（类似于地球上的交配）时，一个 stabard 会充当遗传物质的提供者，而另一个则负责组合这些遗传物质，创造出新的 stabard。显然，组合者的任务要更加艰巨。 聪明的 stabards 早就发现，由于性别众多，每个 stabard 在找到合适的伴侣时都会浪费很多时间。更糟的是，由于机会众多，stabards 还有可能试图通过和多个伴侣建立关系来欺骗当前伴侣，尤其是提供者，因为他们无需担负组合工作的重任。因此，聪明的 stabards 制定了以下规则来规范伴侣关系： 1. 每个 stabard 最多只能形成两个伴侣关系。 2. 为了保持性别间的平衡，一个 stabard 不能在两个伴侣关系中扮演相同的角色（即都作为提供者或都作为组合者）。 3. 伴侣关系的总数量应尽可能多。 聪明的 stabards 每年将他们的数据发送到地球，想要知道在遵循规则的前提下，最多可以形成多少对伴侣关系。

对于每个测试用例，第一行包含两个整数 $M$ 和 $N$，分别表示性别的数量和 stabards 的总数量。接下来有 $M$ 行，每行包含 $M$ 个字符。第 $i$ 行的第 $j$ 个字符表示如果性别为 $i$ 的 stabard 和性别为 $j$ 的 stabard 形成伴侣关系的结果： - 'X' 表示这种关系不允许。 - 'D' 表示性别为 $i$ 的 stabard 为提供者。 - 'C' 表示性别为 $i$ 的 stabard 为组合者。 接着一行包含 $N$ 个空格分隔的整数，每个整数表示一个 stabard 的性别。 若输入的 $M$ 和 $N$ 都为 0，表示输入结束，该测试用例不需处理。总共不会超过 100 个测试用例。

对于每个测试用例，输出一个整数，表示可能形成的最大伴侣关系数量，每组结果占一行。

- 性别数量 $1 \le M \le 50$ - stabards 总数 $1 \le N \le 10^3$ **本翻译由 AI 自动生成**