A strange object has fallen from space onto Alpha Planet! M inhabitants of Alpha Planet have gathered around the object, which looks like a string of length N. Since the inhabitants like palindromes a lot, they want to partition the object into M different pieces such that each inhabitant gets a palindrome. In other words, they want to split the string into M non-overlapping substrings, of which all are palindromes.
They have a special tool that allows them to change characters of the object. Each use of the tool changes 1 character of the object, and the tool can be used up to X times. They want to know whether or not it is possible for each inhabitant to get a palindrome, if they use their special tool up to X times. If it is possible, they also want to know the minimum number of times they need to use the special tool, as it is quite expensive to operate the tool.
A palindrome is a word that is equal to itself when reversed. For example, “program” is not a palindrome while “deed” is. A single letter is a palindrome too.
Constraints:
- 1 <= M <= N <= 100
- 0 <= X <= 20
Input Format:
- First line of input gives the numbers N, M, X, the length of the string, number of inhabitants, and the maximum number of uses of the special tool, respectively
- Second line of input gives the string, consisted of only lowercase letters
Output Format:
- Output “NO” (without quotes) if it is not possible to for every inhabitant to get a palindrome, even after using the tool up to X times
- If it is possible, output “YES” (without quotes) on the first line and the minimum number of uses of the special tool on the second line
Examples:
|
Input |
Output |
Explanation |
3 2 1 abc |
YES 1 |
The answer is “YES” because we can use the special tool to change the ‘c’ to a ‘b’, thus making the partition “a|bb” possible. We print 1 since that is the minimum number of times we used the special tool to make a partition possible. |
5 2 1 abcde |
NO |
The answer is “NO” because no matter which character we change, we cannot partition the string into two palindromes. |
5 3 2 abcde |
YES 1 |
We can find a possible partition by using the special tool to change only 1 character, the ‘e’ to a ‘c’, making the string “abcdc”. We can now partition it into 3 palindromes, “a|b|cdc”. |
(Problem credit: Justin Li)