情太くんは a
から z
までの文字と,
足し算の記号 +
しか知りません.
情太くんには姉の立子さんがいます.
立子さんはそれに加えて,掛け算 *
と括弧 (
,)
,
そして 1
以上 9
以下の整数 (数字) も知っています.
しかし,括弧を多重に使用すること,括弧の中で掛け算を行うことは知りません.
例えば,次のような数式があったとします.
a+a+a
a+4*(b+c)
a+3*(b+2*(c+d))
a-b
a/b
11*a
このうち,情太くんは 1. のみ,立子さんは 1. と 2. を書くことができます. 3. から 6. は二人とも書くことができません.
ある日,情太くんは文字列としての長さが $n$ の多項式 $S$ を書きました.
ショートコーダーの立子さんは,掛け算と括弧と 1
以上 9
以下の整数を使って,$S$ を文字列としてより短い恒等な多項式 $T$ に書きなおしてやりたいと思っています.
しかし,そう簡単ではないようです.
さて,立子さんのかわりに,文字列として最も短い $T$ を作り, その長さを出力するプログラムを書いてください.
$N$
$S$
$1 \leq N \leq 499$
$N$ は奇数である
$S$ は a
から z
までのアルファベット小文字と
+
のみからなる
$S$ の最初の文字はアルファベットであり,その後 +
とアルファベット $1$ 文字が交互に並ぶ
$S$ に同じアルファベットは $9$ 個以下しか含まれない
答えを $1$ 行で出力してください.
5 a+a+a
3
a*3
の $3$ 文字が最短です.
9 a+a+b+a+b
7
a*3+2*b
または a*3+b+b
の $7$ 文字が最短です.
11 a+a+b+a+b+b
7
(a+b)*3
で $7$ 文字
3 a+a
3
a+a
または a*2
で $3$ 文字