← 返回题目列表

AtCoder · typical90_bv

074. ABC字符串2(★6)

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

問題文

现在在电子公告板上 a、 长度由b、 长度由c 组成 显示 N 字符串 使用 S 。

您有以下内容 2 您可以按照您喜欢的任何顺序执行任意数量的操作。然而“改变”原本是 a 什么是 指更改为 b 到,b 什么是 指更改为 c 到,c 什么是 指更改为 a 。

  • S_i = b 是 i (1 \leq i \leq N) 在 1 选择一项, 更改为S_i 在 a 后 更改S_1, S_2, \cdots, S_{i-1} 。
  • S_i = c 是 i (1 \leq i \leq N) 在 1 选择一项, 更改为S_i 在 b 后 更改S_1, S_2, \cdots, S_{i-1} 。

查找可以执行的最大操作数。 是一个字符串

制約

  • 1 \leq N \leq 60
  • S 是 a、 长度由b、 长度由c 组成 显示 N 是一串

入力

输入是按以下格式从标准输入给出的。

N
S

出力

请打印答案。


入力例 1

3
aba

出力例 1

2

例如,通过采取以下步骤, 您可以执行2 操作。

  • 第一 选择 i = 2 并执行操作。那时的弦 更改为 S 是 aba → baa 。
  • 下一步 i = 1 并执行操作。那时的弦 更改为 S 是 baa → aaa 。

入力例 2

10
aaaaaaaaaa

出力例 2

0

所有字符都是 不幸的是,该操作无法执行,因为 a 。


入力例 3

5
baaca

出力例 3

17