AddMul

Time Limit : 2 sec, Memory Limit : 262144 KB

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$ 文字


Source: Ritsumeikan University Programming Camp 2016 , Day 1, Shiga, Japan, 2016-03-06