C: 足し算掛け算 / AddMul

問題文

情太くんは a から z までの文字と， 足し算の記号 + しか知りません． 情太くんには姉の立子さんがいます． 立子さんはそれに加えて，掛け算 * と括弧 (，)， そして 1 以上 9 以下の整数 (数字) も知っています． しかし，括弧を多重に使用すること，括弧の中で掛け算を行うことは知りません．

例えば，次のような数式があったとします．

1. a+a+a
2. a+4*(b+c)
3. a+3*(b+2*(c+d))
4. a-b
5. a/b
6. 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$ 行で出力してください．

サンプル

サンプル入力1

5
a+a+a

サンプル出力1

3

a*3 の $3$ 文字が最短です．

サンプル入力2

9
a+a+b+a+b

サンプル出力2

7

a*3+2*b または a*3+b+b の $7$ 文字が最短です．

サンプル入力3

11
a+a+b+a+b+b

サンプル出力3

7

(a+b)*3 で $7$ 文字

サンプル入力4

3
a+a

サンプル出力4

3

a+a または a*2 で $3$ 文字

Note

Commentary

 

---