Shortest Compressed String After Removal

Delete exactly K consecutive characters, then compress each run of identical characters as "count+character"; a run of a single character is written as just the character. Return the shortest compressed length; K=0 and K=N are allowed. This site keeps the examples as curated in the catalog and computes them from the actual character counts.

This site uses a standard input/output protocol.

输入格式

The first line contains K, and the second line contains an uppercase string S. The catalog ranges are kept: 1≤N≤1000000, 0≤K≤min(100000,N).

输出格式

Output a single integer, the answer.

样例 1

输入：

3
ABBBCCDDCCC

输出：

5

样例 2

输入：

3
AAAAAAAAAABXXAAAAAAAAAA

输出：

3

样例 3

输入：

2
ABCDDDEFG

输出：

6

样例说明

Example 1: deleting DDC leaves ABBBCCCC, compressed to A3B4C with length 5. Example 2: there are 10 A on each side; deleting BXX gives 20A, with length 3. The catalog writes 21A here, which does not match its input; the original snapshot uses 11+10 A, for which its 21A is correct. Example 3: deleting EF gives ABC3DG, with length 6.