配点: 1000 点
問題文
N 草丛排成一排, 它们的编号最大为1 从 N 。 每株植物的高度为 由大于或等于 1 的整数值表示,以及有关它的以下信息: S_1,S_2,\cdots,S_{N-1} 是已知的。
- S_i =
'A':草 i 更多草 i + 1 确实更高 - S_i =
'B':草 i 更多草 i + 1 确实更低 打印
N 草的最小可能高度总和。 仅包含
制約
- 1 \leq N \leq 3000
- N 是一个整数
- S 是
由于它被视为
'A'和 即使增加或减少'B'仅由 N-1 字符串
入力
输入是按以下格式从标准输入给出的。
N S
出力
请将您的答案输出为整数。
入力例 1
7 AABBBA
出力例 1
15
草的各个高度 1, 2, 4, 3, 2, 1, 2 是草的最小总高度的状态。