CF461E Appleman and a Game

Appleman 和 Toastman 喜欢玩游戏。今天他们用字符串玩一个新游戏，规则如下：首先，Toastman 会告诉 Appleman 两个只包含字母 'A'、'B'、'C'、'D' 的字符串 $s$ 和 $t$。然后 Appleman 需要尽快地构造字符串 $s$。最初，他手里是一个空字符串，每秒钟他可以在当前字符串的末尾追加 $t$ 的任意连续子串。 现在，Toastman 和 Appleman 正在开始玩这个游戏。Toastman 已经把字符串 $t$ 告诉了 Appleman，但还没有想好字符串 $s$。Toastman 只想着，他应该选择一个长度为 $n$ 的字符串 $s$。当然，他希望能够为 Appleman 选择一个最难的字符串（即让 Appleman 花费最多时间的字符串）。请你告诉 Toastman，如果他找到了最难的字符串，那么 Appleman 最多会花多少时间。你可以假设 Appleman 玩得最优，也就是说他总是用最少的时间来构造任意字符串 $s$。

第一行是一个整数 $n$（$1 \leq n \leq 10^{18}$）。 第二行是字符串 $t$（$1 \leq |t| \leq 10^{5}$）。字符串 $t$ 只包含字母 'A'、'B'、'C'、'D'。每个字母在 $t$ 中至少出现一次。

输出一个整数 —— Appleman 可能需要用的最多时间。

在第一个样例中，Toastman 可以选择 $s$ 等于 “AAAAA”。 在第二个样例中，Toastman 可以选择 $s$ 等于 “DADDA”。 由 ChatGPT 5 翻译