Alternating Cord Pounces
Gats has a guide cord whose letters form a string . In front of him is a trail of lettered tiles forming a string .
Gats starts before the first trail tile. If he has already covered the first tiles, he is at position . A pounce chooses a length satisfying and , then covers the next trail tiles.
For each pounce, Gats selects one end of the guide cord:
- If he selects the left end, the covered letters must satisfy
After the pounce, Gats moves to position . The guide cord is not changed. Consecutive pounces must select different ends of the cord. Gats may select either end for his first pounce.
Determine the minimum number of pounces needed to reach position , covering the entire trail exactly. If this is impossible, report that no valid sequence exists.
Input
The first line contains three integers , , and (, ), representing the length of the trail, the length of the guide cord, and the minimum pounce length, respectively.
Output
Print the minimum number of pounces required to cover the entire trail. If no valid sequence of pounces exists, print .
Samples
Sample 1
Input
7 4 2 abca abcacab
Output
3
The trail can be covered by abc, ac, and ab, using the left, right, and left ends in that order. Thus, the minimum number of pounces is .
Sample 2
Input
5 3 2 abc ababc
Output
-1
After covering the first ab from the left end, the remaining letters cannot be covered by a pounce from the right end. No valid sequence exists.
Sample 3
Input
5 4 2 abdc cdabd
Output
2
Two pounces cover cd and abd, first using the right end and then the left end.