题目描述

小 Z 有两个字符串 $s,w$, 他可以进行下列三种操作：

1. 从第一个字符串中删去任意一个字符，需要 $a$ 分钟；
2. 在第一个字符串的任意一个位置插入一个字符，需要 $a$ 分钟；
3. 将第一个字符串中某位置上的字符替换成另一个字符，需要 $b$ 分钟。

小 Z 一共有 $k$ 分钟来进行操作，请你告诉小 Z 最少需要多少分钟将 $s$ 转换成 $w$

注意，$|s|$ 不一定等于 $|w|$，即两个字符串的长度不一定相同。

输入格式

从 string.in 文件输入数据。

第一行包括一个字符串 $s$。

第二行包括一个字符串 $w$。

第三行包含三个整数 $a,b,k$。

输出格式

输出到 string.out 文件。

输出最少时间，如果不能再 $k$ 分钟之内完成，输出 $-1$。

样例

aaa
bbbb
0 0 100

0

abab
acac
1 1 100

2

baaaaa
aaaaab
1 100 100

2

aaaaaa
bbbbbb
100 100 0

-1

说明/提示

样例 2 解释

字符串 "abab" 可以通过两次 3 操作将 'b' 替换成 'c'，变成 "acac"，总共耗时 $2$ 分钟。

样例 3 解释

字符串 "baaaaa" 可以通过一次 1 操作删掉 'b'，变成 "aaaaa"，再通过一次 2 操作，插入一个 'b' 变成 "aaaaab"，总共耗时 $2$ 分钟。

数据范围

对于 $20\%$ 的数据，$1 \le |s|,|w| \le 400$.

对于 $60\%$ 的数据，$1 \le |s|,|w| \le 4000$.

对于 $100\%$ 的数据，$1 \le |s|,|w| \le 10^5, 0 \le a,b,k \le 100$，并且字符串 $s,w$ 只包含小写字母。