1788. 神奇的压缩机

【题目描述】

    市面上流行的压缩软件，例如WinRAR，WinZip，都采用了一种经典的压缩算法 Lempel Ziv。虽然LZ算法的解压缩过程效率很高，但由于它在压缩过程中需要动态地建立字符编码，它的压缩过程往往会相当缓慢。因此，许多压缩软件都会使用一种近似算法来提高效率，从而使得压缩效率达不到最高。

    你所在软件公司的CEO Mr.Chang对这种现状很不满意。他希望基于LZ77算法开发出一款最优的压缩软件，叫做WinCHG。它可以将一份文件分割成若干片段，各自独立地进行压缩。作为公司里的骨干，你的任务是对于一个给定的文件片段，计算出下述的压缩算法得到的压缩文件至少要占用多少空间。

    WinCHG产生的压缩文件"*.CHG"包含“普通字符”和“重复块”两种元素。在CHG文件中，一个普通字符占用空间 $A$ 位，一个重复块占用空间 $B$ 位。对于一个普通字符，WinCHG在解压时会将它直接复制到新文件；而一个重复块可以用一个二元组$(r, len)$描述，WinCHG在解压缩时就会从新文件的光标位置之前第$r$位开始将长度为len的一串字符复制到新文件。例如，解压缩程序在读到二元组$(r, len)$前已将$i-1$个字符解压到输出文件T，那么这时它就会将输出文件中的子串$T[i − r ... i − r + len − 1]$再次复制到输出文件。

    注意：$len$可以大于$r$，这时解压缩程序会先将$T[i - r ... i - 1]$复制到输出文件，这时输出文件缺失位置会被填充一部分，解压缩程序就可以将这部分字符再复制到输出文件，依次类推。

【输入格式】

输入文件有两行。

第一行为一个字符串，表示待压缩的文本$T[1 ... N]$。

第二行为两个正整数$A, B$，分别表示压缩文件中一个普通字符和一个重复块所占空间。

【输出格式】

一行一个整数，表示WinCHG所能得到的最小的压缩文件所占空间。

【样例输入】

aaabbaaabababababab 
9 25

【样例输出】

95

【样例解释】

文本可被压缩成aaabb(5,4)(2,10)，最小空间为9 * 5 + 25 * 2 = 95

【数据范围】

\(对于30 \% 的数据，文本长度不大于127,保证输入数据均为小写字母；\)

\(对于70 \% 的数据，文本长度不大于511；\)

\(对于100 \%的数据，文本长度不大于4095，1 \leq A \leq B \leq 32767，输入数据均为大小写字母；\)