Una CPU tiene que ejecutar una lista de tareas, cada una identificada por una letra mayúscula. Cada tarea toma una unidad de tiempo, y en cada unidad la CPU ejecuta una tarea o queda ociosa. Las tareas se pueden hacer en cualquier orden, pero entre dos tareas con la misma letra tienen que pasar al menos \(n\) unidades en las que se hace otra cosa (u ocio). ¿Cuál es el menor tiempo total para terminar todo?

Entrada

La primera línea tiene las tareas, un texto de entre \(1\) y \(10^4\) letras mayúsculas. La segunda tiene \(n\) \((0 \le n \le 100)\).

Salida

El tiempo mínimo.

Ejemplo 1

Entrada

AAABBB
2

Salida

8

Ejemplo 2

Entrada

ACABDB
1

Salida

6

Ejemplo 3

Entrada

AAABBB
3

Salida

10

Basado en el problema 621 de LeetCode, Task Scheduler, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.