Cheap AI

You are a small, stressed mouse trying to survive in the ever–accelerating rise of AI startups. With competitors popping up everywhere, gaining any technological edge feels nearly impossible. In your desperate search for an advantage, you stumble upon $\text{CheapAI}^{\text{TM}}$, a startup so underfunded that even you can afford to work there. Your very first assignment: construct the world's cheapest tokenizer.

You have been hired by CheapAI and assigned the task of building a tokenizer. Unfortunately, the budget is very small, and besides the 26 letters of the English alphabet, you can afford only one additional token, of length at most $K$.

You are given a string $S$ consisting of lowercase English letters and a number $K$. Your goal is to choose a token string of length at most $K$ such that, if you replace some non-overlapping occurrences of your choice of this token in the string with the special character #, the total number of characters required to represent the resulting string is minimized.

Task

Given a number $K$ and a string $S$ consisting of lowercase English letters, choose a non-empty string $t$, with $1 \le |t| \le K$, such that by replacing each occurrence of $t$ in $S$ (chosen so that no two overlap) with the special character #, the total length of the resulting string is minimized.

Determine this minimum length.

Implementation

You should implement the following function:

int solve(int K, std::string S);

This function receives $K$ and $S$ as parameters and must determine the minimum length of the string obtained after replacing some (non-overlapping) occurrences of a chosen token, of length at most $K$, with the character #.

Constraints

• $1 \leq K \leq |S| \leq 200 \ 000$
• $S$ consists of lowercase English letters.

Example 1

input

5
aabaabacbbaabaa

output

7

Explanation

We choose $t$ = aabaa, and the string $S$ becomes #bacbb#, with length $7$.

Example 2

input

8
aaaaaaaaaaaaaaaaaaa

output

4

Explanation

We choose $t$ = aaaaaa, and the string $S$ becomes ###a, of length $4$.