← 返回题目列表

Codeforces · 461/E

E. 苹果人和游戏

中文机器翻译题面 查看原题

Appleman 和 Toastman 喜欢游戏。今天他们玩一个带绳子的游戏,规则如下。首先,Toastman 告诉 Appleman 两个字符串 s 和 t,都只包含字母“A”、“B”、“C”、“D”。那么 Appleman 必须尽快构建 string s。最初他有空字符串,在一秒钟内他可以将 t 的任何连续子字符串附加到当前字符串的末尾。

现在,Toastman 和 Appleman 开始玩游戏。 Toastman 已经将字符串 t 告诉了 Appleman,但他还没有想出字符串 s。 Toastman 只认为,他应该选择由 n 个字符组成的字符串 s。当然,他想为Appleman找到最差的字符串(这样的字符串,Appleman在游戏过程中会花费尽可能多的时间)。告诉 Toastman,如果 Toastman 找到对他来说最差的字符串,Appleman 将在游戏中花费多少时间。您可以假设 Appleman 演奏得最佳,因此他在尽可能短的时间内构建了任何字符串 s。

输入

第一行包含一个整数 n (1 ≤ n ≤ 1018)。第二行包含字符串 t (1 ≤ |t| ≤ 105)。字符串 t 仅包含字母“A”、“B”、“C”、“D”。每个字母在字符串 t 中至少出现一次。

输出

打印一个整数——Appleman 需要的最大可能时间。

示例

输入 #1

5
ABCCAD

输出 #1

5

输入 #2

5
AAABACADBABBBCBDCACBCCCDDDBDCDD

输出 #2

4

注意

在第一个示例中,Toastman 可以选择 s 等于“AAAAA”。

在第二个示例中,Toastman 可以选择等于“DADDA”的 s。