One day, Jerry found a strange typewriter. This typewriter has $2$ input modes: pay $p$ coins to append an arbitrary single letter to the back, or $q$ coins to copy a substring that has already been outputted and paste it in the back. Jerry now wants to write a letter to Tom. The letter is a string $S$ which contains only lowercase Latin letters. But as Jerry is not very wealthy, he wants to know the minimum number of coins he needs to write this letter.
输入解释
This problem contains multiple test cases. Process until the end of file. For each test case, the first line contains string $S$ ($|S| \le 2 \times 10 ^ 5, \sum |S| \leq 5\times 10 ^ 6$), consisting of only lowercase Latin letters. And the second line contains $2$ integers $p$ and $q$ ($1 \leq p,q < 2^{31}$).
输出解释
For each test case, output one line containing the minimum number of coins Jerry needs to pay.