Compressed Representation Size

Delete exactly K consecutive characters, then encode each run of repeated characters as its count followed by the character; a run of length 1 is written as just the character. Find the shortest possible encoding length. The original site's second example was miscalculated, so this site recomputed it independently.

输入格式

This site's input: the first line contains 1..100000 uppercase letters, and the second line contains K (0..N).

输出格式

Output a single integer, the answer.

样例 1

输入：

ABBBCCDDCCC
3

输出：

5

样例 2

输入：

ABCDDDCEFG
2

输出：

7

样例 3

输入：

AAAA
4

输出：

0

样例说明

Example 1: deleting DDC gives ABBBCCCC, encoded as A3B4C with length 5.

Example 2: the shortest length is 7; for example, deleting BC gives ADDDCEFG, encoded as A3DCEFG. The original site's 6 left out characters.

Example 3: deleting all characters leaves an empty encoding of length 0.