Encoding

Time limit1sMemory limit128 MB

Summary

Find the shortest encoding length for a target string under dynamic coding, where a changing marker toggles between verbatim and interpreted modes.

Level: Hard8 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

In most programming languages, a string constant may contain characters that cannot be typed directly on the keyboard. This is usually achieved with a special marker symbol, most often a backslash. Most of the string is read verbatim (exactly as written), and the rest is interpreted in some way.

Professor P. Entropic dislikes using a fixed marker symbol, believing it is far too inflexible — what if you need to encode a string that itself contains many backslashes? He proposes dynamic coding, in which the verbatim and interpreted parts of a string are marked explicitly by a marker symbol that is allowed to change within the string.

An encoded string is decoded from left to right while keeping a current mode (interpreted or verbatim) and a current marker symbol. At the start the mode is interpreted and no marker is set. Then:

While in interpreted mode, if the next two symbols are equal, that symbol becomes the current marker and the pair is consumed without producing any output. This is how the first marker is set and how it is later changed.
A single occurrence of the current marker switches the mode between interpreted and verbatim and produces no output.
Every other symbol produces exactly one output character: an uppercase letter while in interpreted mode, or the lowercase letter itself while in verbatim mode.

Doubled symbols are special only in interpreted mode; in verbatim mode a repeated symbol is simply two verbatim characters.

For example, over the alphabet $\{a, b, c\}$ the encoded string cccabcabcaacbbcaac decodes to abABaaCC, where the uppercase letters are the interpreted part and the lowercase letters are read verbatim.

Professor Entropic wants to measure how space-efficient dynamic coding is. You are given a target string in which the verbatim part is written in lowercase and the interpreted part in uppercase. Determine the length of its shortest possible encoding.

Input

The first line contains an integer $k$ ( $2 \le k \le 26$ ) — the size of the alphabet, which consists of the first $k$ lowercase letters of the English alphabet.

The second line contains the target string. Characters to be read verbatim are written in lowercase and characters to be interpreted are written in uppercase; every letter, ignoring case, is one of the first $k$ letters. The string contains at most $100\,000$ characters.

Output

Print a single integer — the number of characters in the shortest encoding of the given string under the dynamic coding scheme.

Examples4

Example 1
Input
```
3
abABaaCC
```
Expected output
```
18
```
Example 2
Input
```
2
A
```
Expected output
```
1
```
Example 3
Input
```
2
a
```
Expected output
```
4
```
Example 4
Input
```
3
ABC
```
Expected output
```
3
```