编辑距离

题目描述

把字符串 X 变成字符串 Y：在 X 中插入一个字符代价 $c_i$、删除一个字符代价 $c_d$、替换一个字符代价 $c_r$。求最小总代价。

输入格式

第一行三个整数 $c_i, c_d, c_r$；第二行 X；第三行 Y。允许空串（对应空行）。

输出格式

一行一个整数。

数据范围

串长 $\le 2000$（允许空串），字符为小写字母；$1 \le c_i, c_d, c_r \le 10^4$

答案可能超出 32 位整数，请使用 64 位整数。