Make a Periodic String

Time limit2sMemory limit128 MB

Summary

Given a DNA string and a bound M, find the minimum number of character edits to make the string periodic with some period length at most M.

Level: Medium5 of 10
Topics: String, Greedy, Brute force, Implementation
Solved: No attempts yet

Problem

Sejun is a biologist, so he often works with DNA strings. One day, he became tired of looking at a long DNA string and wanted to express it in a simpler periodic form.

For a string of length $L$ , a positive integer $P$ is a period length if, for every integer $i$ with $0 \le i \le L-P-1$ , the character at position $i$ is the same as the character at position $i+P$ . For example, CATCATC, CATCAT, ACTAC, and ACT all have period length $3$ .

Given a DNA string, change as few characters as possible so that it becomes a periodic string whose period length is at most $M$ . Find the minimum number of characters that must be changed.

Input

The first line contains $M$ . The value of $M$ is at most the length of the string.

The second line contains the DNA string. The string consists only of A, C, G, and T, and its length is at most $3000$ .

Output

Print the minimum number of characters that must be changed.

Examples4

Example 1
Input
```
2
ACGTGCA
```
Expected output
```
3
```
Example 2
Input
```
3
ATAGATA
```
Expected output
```
1
```
Example 3
Input
```
13
ACGCTGACAGATA
```
Expected output
```
0
```
Example 4
Input
```
1
AAAATTTCCG
```
Expected output
```
6
```