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.

Input Specification

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 Specification

Output the minimum possible value of ~c_a^2 + c_b^2 + \ldots + c_z^2~ for Jonathan.

Subtasks

Subtask 1 [30%]

~L = 0~

Subtask 2 [70%]

No further constraints.

Sample Input 1

abcdefghijkllllll
0 5

Sample Output 1

12

Sample Input 2

rimuruclasher
3 2

Sample Output 2

8