One day, Jerry found a strange typewriter. This typewriter has 22 input modes: pay pp coins to append an arbitrary single letter to the back, or qq 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 SS 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.
Input
This problem contains multiple test cases. Process until the end of file. For each test case, the first line contains string SS (|S|≤2×105,∑|S|≤5×106|S|≤2×105,∑|S|≤5×106), consisting of only lowercase Latin letters. And the second line contains 22 integers pp and qq (1≤p,q<2311≤p,q<231).
Output
For each test case, output one line containing the minimum number of coins Jerry needs to pay.