Jonathan is given a string ~S~ containing solely lowercase english letters. He is asked to perform the two following operations in order exactly once:
- Remove a substring of length up to ~L~ (inclusive) from the string.
- Remove up to ~K~ (inclusive) characters from the remaining string.
Let ~c_a~ be the number of
a's in the resultant string, ~c_b~ be the number of
b's, etc. Jonathan's goal is to minimize ~c_a^2 + c_b^2 + \ldots + c_z^2~ after performing the two operations. What is the minimum possible value?
Python users are recommended to use PYPY over CPython. There is a significant performance increase.
The first line will contain the string ~S\ (1 \le |S| \le 10^5)~. ~S~ will only contain lowercase english letters.
The second line will contain two integers, ~L, K\ (0 \le L, K \le |S|)~.
Output the minimum possible value of ~c_a^2 + c_b^2 + \ldots + c_z^2~ for Jonathan.
Subtask 1 [30%]
~L = 0~
Subtask 2 [70%]
No further constraints.
Sample Input 1
abcdefghijkllllll 0 5
Sample Output 1
Sample Input 2
rimuruclasher 3 2
Sample Output 2