Migrated from Lutece 2771 代码查重

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

LiZnB 需要编写一个用于动态规划专题的代码查重程序。他提出了用以下方法来计算两份代码的重合度。

对于字符串 $a$ 和 $b$, 他们的重合度 $f(a, b)$ 定义为。

$f(a, b) = x \cdot LCS(a, b) - y \cdot |a| - z \cdot |b| $

其中 $LCS(a, b)$ 表示 $a$, $b$ 两个字符串的最长公共子序列 (The Longest Common Subsequence) 长度。$x, y, z$ 为传入查重程序的三个参数。$|a|$ 和 $|b|$ 分别表示字符串 $a, b$ 的长度。

对于两份代码 $A, B$, 可以视其为两个字符串，$A$ 的任意一个子串(Substring) $a$, 和 $B$ 的任意一个子串 $b$ 的重合度为 $f(a, b)$。 LiZnB 定义两份代码的重合度为所有的 $f(a, b)$ 中的最大值。他希望得到两份代码 $A, B$ 的重合度。

因为 LiZnB 需要给动态规划专题出题，没有时间完成这个程序。所以他想让你帮他完成这个程序。

请注意：

1. 子串(Substring)：如果 $a$ 是 $b$ 的子串，那么可以通过删除 $b$ 开头几个字符(可以是 $0$ 个或者全部)，和 $b$ 结尾几个字符(可以是 $0$ 个或者全部)得到 $a$。
2. 子序列(Subsequence)：如果 $a$ 是 $b$ 的子序列，那么可以通过删除 $b$ 中任意几个字符(可以是 $0$ 个或者全部)得到 $a$。
3. 空串也是子串。
4. 题目描述纯属虚构，请勿当真。但一定不要抄袭！

Input

第一行 $5$ 个正数 $n, m, x, y, z$ ($1 \leq n, m, x, y, z\leq 5000$), 分别表示字符串 $A, B$ 的长度，和三个参数。 第二行一串字符串，仅含小写字母，表示代码 $A$。 第三行一串字符串，仅含小写字母，表示代码 $B$。

Output

一行，一个整数，表示最大的 $f(a, b)$。

Samples

5 5 1 1 1
aaaaa
aaaaa

0

2 3 4 1 1
ab
aba

4

3 4 5000 1000 1000                              
aba
baba

9000

10 7 5000 2021 2022
codeforces
atcoder

3828

6 5 8 2 1
define
using

10

Note

对于第一个样例：可以证明最优选择是空串。 对于第二个样例：$A, B$ 都选择子串 ab，$f(a, b) = 4 \times 2 - 1 \times 2 - 1 \times 2 = 4$。

Resources

2022 UESTC ICPC Training for Dynamic Programming