Task Scheduler

Each time slot either runs one task or stays idle, and all tasks can be reordered; two runs of tasks with the same letter must be separated by at least cooldown other slots. Find the minimum number of slots needed to finish everything.

输入格式

The first line contains the task string and the second line contains cooldown. Original bounds: 1..10000 tasks, letters A..Z, and 0≤cooldown≤100.

输出格式

Output a single integer, the answer.

样例 1

输入：

AAABBB
2

输出：

8

样例 2

输入：

ACABDB
1

输出：

6

样例 3

输入：

AAABBB
3

输出：

10

样例说明

The outputs of the three public examples are 8; 6; and 10, checked by independent enumeration or direct simulation.