Appleman and a Game

题意翻译

给定一个串 $t$，由 `A`，`B`，`C`，`D` 四种字符构成且每种字符至少出现一次。有一个空串，每次可以选 $t$ 的一个子串加在它后面。求一个长度为 $n$ 字符集为 `ABCD` 的串 $s$，最大化以上述操作得到 $s$ 的最小操作次数，输出这个最大值。

题目描述

Appleman and Toastman like games. Today they play a game with strings with the following rules. Firstly Toastman tells Appleman two strings $ s $ and $ t $ both consisting only of letters 'A', 'B', 'C', 'D'. Then Appleman must build string $ s $ as quickly as possible. Initially he has empty string, and in one second he can append to end of the current string any contiguous substring of $ t $ . Now, Toastman and Appleman are beginning to play the game. Toastman has already told string $ t $ to Appleman, but he hasn't come up with string $ s $ yet. Toastman only thinks, that he should choose string $ s $ consisting of $ n $ characters. Of course, he wants to find the worst string for Appleman (such string, that Appleman will spend as much time as possible during the game). Tell Toastman, how much time will Appleman spend during the game if Toastman finds the worst string for him. You can assume that Appleman plays optimally, therefore he builds any string $ s $ in minimal possible time.

输入输出格式

输入格式

The first line contains an integer $ n $ ( $ 1<=n<=10^{18} $ ). The second line contains string $ t $ ( $ 1<=|t|<=10^{5} $ ). String $ t $ consists of only letters 'A', 'B', 'C', 'D'. Each letter appears at least once in string $ t $ .

输出格式

Print a single integer — the largest possible time Appleman needs.

输入输出样例

输入样例 #1

5
ABCCAD

输出样例 #1

5

输入样例 #2

5
AAABACADBABBBCBDCACBCCCDDDBDCDD

输出样例 #2

4

说明

In the first example, Toastman can choose $ s $ equal to "AAAAA". In the second example, Toastman can choose $ s $ equal to "DADDA".