Task Scheduler

Problem statement

A processor handles unit-time jobs identified by uppercase letters. Jobs with the same letter require a cooldown before that letter can run again, but the scheduler may reorder jobs and insert idle intervals when necessary. Your task Find the minimum number of time intervals required to finish every task. Between two executions of the same letter, at least cooldown other intervals must occur. Important details Every task takes one interval. An interval may contain a different task or be idle. Reordering is allowed, but no task can be omitted. A zero cooldown permits identical tasks consecutively. Worked example For tasks AAAB and cooldown 2, one optimal schedule is A B idle A idle idle A. It takes 7 intervals; three A tasks require two gaps of length 2.

Input format

First line: n cooldown. Second line: a string of n uppercase task letters.

Output format

Print the minimum interval count.

Constraints

1 <= n <= 10000; 0 <= cooldown <= 100; task letters A-Z.

Sample input

4 2
AAAB

Sample output

7