Find Minimum Time Required (Amazon Bangalore :)

Each character is a task that takes 1 unit of time, and identical characters belong to the same type. You may reorder the tasks freely and insert idle time; two tasks of the same type must be separated by at least minGap full time units. Find the minimum time to finish all tasks.

输入格式

The first line contains the lowercase task string; the second line contains minGap. This site uses 1≤string length≤100000, 0≤minGap≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

aaabbb
2

输出：

8

样例 2

输入：

aaabbb
0

输出：

6

样例 3

输入：

abacadaeafag
2

输出：

16

样例说明

Example 1: ab_ ab_ ab (spaces are only for grouping) takes 8 units, with 2 units between tasks of the same type. Example 2: there is no gap requirement, so the 6 tasks run back to back and the answer is 6. Example 3: a has 6 tasks, which need at least 16 units from the first to the last; other tasks can fill the gaps, so the answer is 16.