I. Backup Ink
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A print shop represents a strip of paper by a string $$$s$$$ of length $$$n$$$. Each position of the string corresponds to a cell of the strip.

To test a pattern $$$t$$$, which must be a non-empty substring of $$$s$$$, the print shop starts with all cells unpainted. Then it performs one ink application for each occurrence of $$$t$$$ in $$$s$$$.

If an occurrence starts at position $$$i$$$, its application paints all the cells of the interval $$$[i, i + |t| - 1]$$$. Applications may overlap: a cell is considered painted as long as at least one application covers it.

The print shop wants to measure what happens if an application fails. To do so, it cancels exactly one of the applications and keeps all the others. The damage of that cancellation is the number of cells that were painted and stop being painted.

A pattern is resilient if the damage is at most $$$k$$$, no matter which of its applications is cancelled.

Compute how many distinct non-empty substrings of $$$s$$$ are resilient.

The tests of different patterns and the different cancellations are considered independently. Cancelling an application does not modify the characters of $$$s$$$ nor the positions of its occurrences. The pattern does not need to paint the whole strip.

Two substrings are considered equal if they have the same length and the same characters, even if they appear at different positions.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \times 10^{5}$$$, $$$0 \leq k \leq n$$$): the length of the string and the maximum allowed damage.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting only of lowercase letters of the English alphabet.

Output

Print an integer: the number of distinct non-empty substrings that are resilient.

The answer may not fit in a 32-bit integer.

Examples
Input
5 1
aaaaa
Output
4
Input
15 1
aaaaabaaabaaaaa
Output
4
Input
3 3
abc
Output
6
Note

Explanation for example 1

The resilient patterns are a, aa, aaa and aaaa.

For example, aaa occurs in the intervals $$$[1,3]$$$, $$$[2,4]$$$ and $$$[3,5]$$$. When the first application is cancelled, only cell $$$1$$$ stops being painted. When the middle application is cancelled, no cell stops being painted. When the last one is cancelled, only cell $$$5$$$ stops being painted.

The pattern aaaaa is not resilient: it has a single occurrence and, when its application is cancelled, all five cells stop being painted.

Explanation for example 2

The resilient patterns are a, b, aa and aaaa.

The pattern aaa is not resilient: when the application corresponding to $$$[7,9]$$$ is cancelled, the three cells of that interval stop being painted.

On the other hand, aaaa occurs in $$$[1,4]$$$, $$$[2,5]$$$, $$$[11,14]$$$ and $$$[12,15]$$$. Cancelling any of those applications causes a damage of one cell.

Explanation for example 3

All distinct substrings are resilient: a, b, c, ab, bc and abc. Each of them has a single occurrence, but cancelling its application causes a damage of at most $$$3$$$.