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+\cdots +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+\cdots +c_z^2$ for Jonathan.

Constraints

Subtask 1 [30%]

$L=0$

Subtask 2 [70%]

No additional constraints.

Sample Input 1

abcdefghijkllllll
0 5

Sample Output 1

12

Sample Input 2

rimuruclasher
3 2

Sample Output 2

8