题目描述

邻居们又在找谢别克的麻烦，并给他想出了新的挑战。这次他们有一段长度为 $n$ 的线段。邻居们把谢别克放在了坐标 $0$ 处，并要求他跳到坐标为 $n$ 的点。

但谢别克有个问题。他只能向前跳跃长度 $1$、$2$ 或 $3$。然而邻居们决定进一步限制他。他们给了他一个长度为 $m$、由小写拉丁字母组成的字符串 $s$。谢别克可以向前跳跃长度 $x$ ($1 \leq x \leq 3$)，当且仅当在字符串 $s$ 中存在一个子串，满足以下条件：

• 该子串的长度为 $x$。
• 子串中的所有字母都相同。
• 在子串的左侧，要么是一个不同于子串字母的字符，要么不存在任何字符（即子串位于字符串边缘）。
• 在子串的右侧，要么是一个不同于子串字母的字符，要么不存在任何字符。

如果字符串 $a$ 可以通过从 $b$ 的开头删除若干个（可以是零个或全部）字符，并从结尾删除若干个（可以是零个或全部）字符得到，则称 $a$ 是 $b$ 的子串。

例如，假设字符串为 aabaaabbcbbbebbab 且 $x=2$。那么该字符串中有多个子串符合限制条件：(aa)baaa(bb)cbbbe(bb)ab。因此在这种情况下，可以跳跃长度为 $2$。此外，该字符串也允许跳跃长度为 $1$ 和 $3$。而字符串 ebbbcedddd 只允许跳跃长度 $1$ 和 $3$。

谢别克需要仅使用允许的跳跃长度，从点 $0$ 跳到坐标为 $n$ 的点，并且使用最少的跳跃次数。假设你就是谢别克，请计算这个最少的跳跃次数。

请注意，谢别克需要恰好跳到坐标为 $n$ 的点，而不是 $n+1$ 或 $n+2$。

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 1\,000\,000\,000$) —— 谢别克需要跳跃的线段长度。

第二行包含一个整数 $m$ ($1 \leq m \leq 200\,000$) —— 邻居给出的字符串长度。

第三行包含一个长度为 $m$ 的字符串 $s$，由小写字母组成 —— 邻居给出的字符串。

输出格式

输出一个整数 —— 谢别克为了从坐标为 $0$ 的点跳到坐标为 $n$ 的点所需的最少跳跃次数。如果他无法完成，则输出 $-1$。

4
5
acccz

2

11
18
bbbccccdddbcggggga

5

10
5
zzzzz

-1

提示

样例说明

• 谢别克可以跳跃 $1$ 和 $3$。一种可能的跳跃方案是 $1 + 3 = 4$。
• 谢别克可以跳跃 $1$ 和 $3$。一种可能的跳跃方案是 $1 + 3 + 3 + 1 + 3 = 11$。
• 谢别克完全无法跳跃，因为唯一由相同字母组成的子串长度为 $5$。

翻译由 DeepSeek V3 完成