乌龟对对碰

题目描述

Y 同学正在观察一场“乌龟对对碰”游戏。

游戏使用一个 $3\times3$ 的棋盘，共有 $9$ 个位置，按照从左到右、从上到下的顺序编号为：

共有 $n$ 只乌龟，按照 $1\sim n$ 编号。第 $i$ 只乌龟的颜色为 $a_i$，颜色使用数字 $0\sim9$ 表示。

此外，给定一种幸运颜色 $x$。

游戏中维护两个整数：

• 乌龟计数器：初始值为 $0$；
• 乌龟数量限制：初始值为 $m$。

游戏按照以下流程进行。

放置乌龟

按照编号从小到大的顺序依次取出尚未处理的乌龟。

每取出一只乌龟：

1. 乌龟计数器增加 $1$；
2. 将这只乌龟放入棋盘中编号最小的空位置；
3. 如果这只乌龟的颜色等于幸运颜色 $x$，则乌龟数量限制增加 $1$。

每放入一只乌龟后，如果满足以下任意一个条件，则立即进行一次结算：

• 棋盘上的 $9$ 个位置已经全部放满；
• 乌龟计数器已经达到乌龟数量限制。

结算规则

结算时按照以下 $6$ 条规则依次检查。

规则编号越小，优先级越高。每执行完一条规则后，都需要重新从规则 $1$ 开始检查，直到所有规则均无法执行为止。

规则 1：全家福

如果当前棋盘上所有乌龟的颜色两两不同，则销毁棋盘上的所有乌龟，并令乌龟数量限制增加 $8$。

规则 2：同行

如果存在某一行的 $3$ 个位置均有乌龟，并且这 $3$ 只乌龟颜色相同，则销毁这 $3$ 只乌龟，并令乌龟数量限制增加 $2$。

规则 3：同列

如果存在某一列的 $3$ 个位置均有乌龟，并且这 $3$ 只乌龟颜色相同，则销毁这 $3$ 只乌龟，并令乌龟数量限制增加 $2$。

规则 4：对角线 1

如果位置 $1,5,9$ 上均有乌龟，并且这 $3$ 只乌龟颜色相同，则销毁它们，并令乌龟数量限制增加 $2$。

规则 5：对角线 2

如果位置 $3,5,7$ 上均有乌龟，并且这 $3$ 只乌龟颜色相同，则销毁它们，并令乌龟数量限制增加 $2$。

规则 6：碰

从位置 $1$ 到位置 $9$ 依次检查。

对于当前检查的位置 $i$，如果该位置有乌龟，并且存在另一个位置 $j$，使得位置 $j$ 上的乌龟与位置 $i$ 上的乌龟颜色相同，则：

• 若有多个满足条件的位置 $j$，选择编号最小的一个；
• 销毁位置 $i$ 和位置 $j$ 上的两只乌龟；
• 乌龟数量限制增加 $1$。

执行完本次操作后，重新从规则 $1$ 开始检查。

游戏结束

一次结算结束后：

• 如果乌龟计数器仍小于乌龟数量限制，并且还有尚未处理的乌龟，则继续按照编号顺序放置乌龟；
• 否则游戏结束。

请你求出游戏结束时乌龟计数器的值。

输入格式

第一行包含三个整数 $n,m,x$，分别表示乌龟数量、初始乌龟数量限制以及幸运颜色。

第二行包含一个长度为 $n$ 的字符串。

字符串的第 $i$ 个字符表示第 $i$ 只乌龟的颜色 $a_i$，每个字符均为 0 到 9 中的一个数字。

输出格式

输出一行一个整数，表示游戏结束时乌龟计数器的值。

样例

样例输入 #1

27 10 3
012345678999892922167450000

样例输出 #1

23

样例解释

乌龟计数器 $0$、初始乌龟限制：$10$、幸运颜色为 $3$。

第一轮

012345678999892922167450000
~~~~~~~~~

拿了 $9$ 个乌龟，乌龟计数器变为 $9$，乌龟限制变为 $11$（触发了一次幸运颜色）

结算时触发了第一条规则，棋盘清空，乌龟限制变为 $19$（【全家福】 $+8$）

第二轮

012345678999892922167450000
xxxxxxxxx~~~~~~~~~

拿了 $9$ 个乌龟，乌龟计数器 $18$，乌龟限制 $19$

【同行$+2$】 乌龟限制变为 $21$，棋盘变为：

【碰$+1$】 乌龟限制变为 $22$，棋盘变为：

【碰$+1$】 乌龟限制变为 $23$，棋盘变为：

第三轮

012345678999892922167450000
xxxxxxxxxxxxxxxxxx~~~~~

拿了 $5$ 个乌龟，乌龟计数器 $23$，乌龟限制 $23$

没有触发任何结算规则，游戏结束。

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1\le n\le1000$；
• $1\le m\le100$；
• $0\le x\le9$；
• $a_i\in{0,1,\dots,9}$；
• 最终乌龟计数器的值不超过 $n$。

• 特殊性质 A：保证 $m\ge n$。
• 特殊性质 B：保证所有乌龟的颜色均不等于幸运颜色 $x$。
• 特殊性质 C：保证所有乌龟的颜色均相同。