Ducks in a Row

Sri is playing a game with ducks, geese, and a magic wand. He first puts all of his ducks in a row. His friend Srinivas then inserts some geese between the ducks at various places. After that, Sri uses the wand to flip some of the birds.

One use of the wand works like this:

1. Sri picks a contiguous stretch of the row.
2. Every bird in that stretch that was a duck becomes a goose.
3. Every bird in that stretch that was a goose becomes a duck.

Sri meets his objective when the row holds at least $k$ maximal runs of ducks of length at least $n$. A maximal run of ducks is a block of consecutive ducks with no duck immediately to its left and no duck immediately to its right. For example, DDGGGGDDDGDDDGD holds 4 maximal runs of ducks, of lengths 2, 3, 3, and 1.

Other maximal runs of ducks may remain when the game ends, including runs shorter than $n$. Only the number of runs of length at least $n$ matters.

Find the minimum number of wand uses that lets Sri meet his objective.

The first line contains two integers $n$ and $k$ ($1 \le n, k \le 2000$), where $n$ is the minimum length Sri wants for each run of ducks and $k$ is the minimum number of such runs.

The second line contains a string $s$ ($1 \le |s| \le 2000$) consisting of the capital letters D and G only. It describes the row of birds before Sri uses the wand, where D is a duck and G is a goose.

Print a single integer, the minimum number of wand uses needed to meet the objective, or -1 if the objective cannot be met.