1650: 字符串压缩B

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:2 Solved:2

Description

行程长度编码是一种常用的字符串压缩方法,它将连续的相同字符(重复2次或更多次)替换为字符和表示字符计数的数字(行程长度)。例如,用此方法压缩字符串"aabccc",将"aa"替换为"a2","ccc"替换为` "c3"。因此压缩后的字符串变为"a2bc3"。注意,本问题中,压缩时没有在单个字符后附加计数'1'。

给定一个字符串s和一个整数k。你需要从字符串s中删除最多k个字符,以使s的行程长度编码长度最小。请返回删除最多k个字符后,s行程长度编码的最小长度。

Input

第一行,输入字符串s(1<=|s|<=100,s 仅包含小写英文字母)

第二行,输入删除的字符数k(0 <= k <= |s|)

Output

输出行程长度编码的最小长度。

Sample Input Copy

aaabcccd
2

Sample Output Copy

4

HINT

【样例1说明】

在不删除任何内容的情况下,压缩后的字符串是 "a3bc3d" ,长度为 6 。最优的方案是删除 'b' 'd',这样一来,压缩后的字符串为 "a3c3" ,长度是 4


【输入样例2】

aabbaa

【输出样例2】

2

【样例2说明】

如果删去两个 'b' 字符,那么压缩后的字符串是长度为 2 "a4"


【输入样例3】

aaaaaaaaaaa

0

【输出样例3】

3

【样例3说明】

由于 k 等于 0 ,不能删去任何字符。压缩后的字符串是 "a11" ,长度为 3