题目描述

定义由连续k个A、连续k个B、连续k个C构成的字符串为k阶ABC字符串，注意一定要按照ABC的顺序。比如，AABBCC为一个2阶的ABC字符串，但BBAACC不是合法的2阶ABC字符串。

现在有一个只包含A、B、C的字符串S，我们可以对它进行如下3种操作： 操作1：删除S开头的一个字符 操作2：删除S结尾的一个字符 操作3：删除S中间的一个字符。

现在我们想通过多次操作，把字符串S变成一个k阶的ABC字符串，又希望操作3的使用次数尽可能少。请求出把字符串S变成k阶ABC字符串，使用操作3的最小次数是多少？如果不能变成k阶ABC字符串，则输出-1。

输入格式

第一行为一个整数k，为构造的ABC字符串的阶数。 第二行为一个只包含A、B、C的字符串，为我们要操作的字符串S。

输出格式

一行，一个整数，表示操作3的最小使用次数，如果无解则输出-1。

样例

2
BACABCBCCA

2

3
CCCBBBAAA

-1

样例解释

1. 进行一次操作1，变为ACABCBCCA。
2. 进行一次操作2，变为ACABCBCC。
3. 进行一次操作3，删掉第2个字符，变为AABCBCC。
4. 进行一次操作3，删掉第4个字符，变为AABBCC。

数据范围

• 对于 $20\%$ 的数据：$3 \le n \le 21$
• 对于 $30\%$ 的数据：$3 \le n \le 3000$
• 对于 $100\%$ 的数据：$3 \le n \le 2 \times 10^5$，$1 \le k \le n / 3$