User scheduling problem

■ Title Description

A positive integer array is given to represent the task list to be executed by the system , Each element of the array represents a task , The value of the element indicates the type of the task .

Please calculate the minimum time required to complete all tasks .

The task execution rules are as follows :

Tasks can be executed in any order , And the execution time of each task is 1 Time units .
Two tasks of the same type must have a length of N Cooling time of units , such as N by 2 when , In time K Type executed 3 The task of , that K+1 and K+2 Two time cannot execute type 3 Mission .
The system can perform a task in any unit of time , Or waiting state .
explain ： The maximum length of the array is 1000, Maximum speed 1000.

Input description

The first line records an array separated by half width commas , Array length not more than 1000, The value of the array element does not exceed 1000,
The second line records the task cooling time ,N As a positive integer ,N<=100.
Output description

The output is the minimum time required to complete all tasks .
Example 1 Input and output examples are for debugging only , The background judgment data generally does not contain examples

Input

2,2,2,3

2

Output

7

explain

Time 1： Execution type 2 Mission .
Time 2： Execution type 3 The task of （ Because the cooling time is 2, So time 2 Cannot execute type 2 The task of ）.
Time 3： The system waits （ Still in type 2 The cooling time of ）.
Time 4： Execution type 2 Mission .
Time 5： The system waits .
Time 6： The system waits .
Time 7： Execution type 2 Mission .
So it takes a total of 7.

def task_schedule():
    arr = input().strip().split(",")
    n = int(input().strip())
    d = {
    } 
    d_max = 0 
    d_max_n = 0  
    for i in arr:
        d[i] = d.get(i, 0) + 1
        if d[i] > d_max:
            d_max = d[i]
    for k, v in d.items():
        if d[k] == d_max:
            d_max_n += 1
    return max((d_max - 1) * (n + 1) + d_max_n, len(arr))


if __name__ == "__main__":
    print(task_schedule())