有一天,Nikita 发现只包含字母“a”和“b”的字符串。
Nikita 认为,如果可以在不改变字母顺序的情况下将字符串切割成 3 个字符串(可能是空的),其中第 1 个和第 3 个字符串仅包含字母“a”,第 2 个字符串仅包含字母“b”,那么该字符串就是美丽的。
Nikita 希望通过删除一些(可能没有)字符来使字符串变得漂亮,但不改变它们的顺序。他能得到的字符串最大长度是多少?
输入
第一行包含一个长度不大于5 000的非空字符串,仅包含小写英文字母“a”和“b”。
输出
打印一个整数——Nikita 可以获得的漂亮字符串的最大可能大小。
示例
输入 #1
abba
输出 #1
4
输入 #2
bab
输出 #2
2
注意
这是第一个样本,字符串已经很漂亮了。
在第二个示例中,他需要删除“b”之一以使其美观。