题目描述

你要借助一个栈打印一个仅由 $\red{ABC }$组成的字符串 $\red{S. }$初始时栈为空，每次操作可以为以下三种之一：

$\red{1.}$压入一个字符到栈顶；

$\red{2.}$弹出当前的栈顶元素（需保证栈非非非空空空）；

$\red{3.}$打印当前的栈顶字符（需保证栈非非非空空空）。

结束操作后你要保证栈依依依然然然为为为空空空；求打印出 $\red{S }$的最少操作次数。

输入格式

仅一行一个非空字符串 $\red{S(1 ≤}$ $\red{|S| ≤}$ $\red{5000). }$

输出格式

输出一个整数表示答案。

样例

输入样例1

ABCCBA

输出样例1

12

输入样例2

AAABAAB

输出样例2

13

输入样例3

ABCBCBACBACBCBABCA

输出样例3

38

输入样例4

ABCBCBCABCBABCBCABCBABCBACBABCBCBABA

输出样例4

74

提示

栈是一种后进先出的线性表。

我们用 $\red{ABC }$表示压入一个相应字符，$\red{P }$表示弹栈，$\red{Q }$表示打印。

样例 $\red{1 }$的一个最优的操作序列如下： $\red{AQBQCQQPQPQP}$

样例 $\red{2 }$的一个最优的操作序列如下： $\red{AQQQBQPQQBQPP}$