Problem D
Jungle Play
Edna the Echidna is playing a game with a fish called Wanda.
Edna arranged $N$ cups in front of Wanda and put a little ball under one of them. Wanda wants to find the ball, and for that she uses a powerful water stream to knock a cup of her choice over. If Wanda chooses the cup with the ball she wins. If she doesn’t, Edna resets the cup and Wanda tries again.
Edna and Wanda are old friends and know each other well. In particular, Edna knows exactly in what order Wanda will knock the cups over.
Edna is having a blast and wants the game to last for a very long time! She can distract Wanda up to $K$ times and instantaneously move the ball to any other cup.
If Edna acts the best way she can, for how long will the game last?
Input
In the first line of input there are three integers: the number of cups $N$ ($1 \le N \le 26$), the number of times Edna can distract Wanda $K$ ($0 \le K \le 10^6$), and the number of cups Wanda will try knocking over before getting tired $M$ ($1 \le M \le 10^6$).
The second line of input contains a single string with $M$ characters, each one is a lower case letter from the first $N$ letters of the alphabet. This represents in what order Wanda will try to knock the cups over.
Output
The output should consist of a single line with how many cups Wanda will knock over until she finds the ball, or $-1$ is she doesn’t find it at all.
Sample
On sample $2$ below, Edna will start by putting the ball under cup c, and will change to cup a right before the fifth try by Wanda. Wanda will eventually find the ball on her seventh try.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 0 10 abbacbacca |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1 10 abbacbacca |
7 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 3 10 abbacbacca |
-1 |
