压缩

题目描述

行程长度编码是一种常用的字符串压缩方式。它会把连续出现的相同字符压缩成“字符 + 次数”的形式：

• 若某个字符只出现 1 次，则只保留字符本身；
• 若某个字符连续出现超过 1 次，则压缩为 字符 + 次数。

例如：

• "aabccc" 可以压缩为 "a2bc3"；
• 压缩后字符串 "a2bc3" 的长度为 5。

现在给定一个只由小写字母组成的字符串 s 和一个整数 k，你最多可以从字符串中删除 k 个字符。

请你计算：在最多删除 k 个字符后，字符串压缩结果的最小可能长度。

输入格式

第一行输入一个字符串 s。

第二行输入一个整数 k。

输出格式

输出一个整数，表示最小可能的压缩长度。

数据范围

1 <= |s| <= 100

0 <= k <= |s|

字符串 s 仅由小写字母组成。

样例 1

输入

aaabcccd
2

输出

4

说明

删除 b 和 d 后，字符串变为 "aaaccc"，压缩结果为 "a3c3"，长度为 4。