Rate-Limiting Algorithm

There are n requests, each taking 1 time unit, and requests[i] in the string gives the region the request belongs to. You may reorder the requests freely and insert idle time; two requests from the same region must be separated by at least minGap full idle time units. Find the shortest time needed to finish all requests.

The gap semantics are established by the official examples of Amazon #175, which has the same statement; the three illustrative examples below are taken from #175.

输入格式

The first line contains n (1 ≤ n ≤ 100000); the second line contains a lowercase string requests of length n; the third line contains minGap (0 ≤ minGap ≤ 100).

输出格式

Output a single integer, the answer.

样例 1

输入：

6
aaabbb
2

输出：

8

样例 2

输入：

6
aaabbb
0

输出：

6

样例 3

输入：

12
abacadaeafag
2

输出：

16

样例说明

The first three illustrative examples come from Amazon #175, which has the same rules, and make clear that minGap is the number of idle time units between requests of the same type.