该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

定义由连续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。

样例输入1

2
BACABCBCCA

样例输出1

2

样例输入2

3
CCCBBBAAA

样例输出2

-1

样例解释1

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

数据范围

对于20%的数据保证：设字符串S的长度为n，必有3<=n<=21。 对于30%的数据保证：设字符串S的长度为n，必有3<=n<=3000。 对于100%的数据保证：设字符串S的长度为n，必有3<=n<=2×10^5，1<=k<=n/3。