One day, Jerry found a strange typewriter. This typewriter has 2 input modes: pay coins to append an arbitrary single letter to the back, or 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 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.
输入描述:
The first line contains string which contains only lowercase Latin letters.
The second line contains 2 integers and
输出描述:
Output one line containing the minimum number of coins Jerry needs to pay.