一家跨国公司正请求你帮助他们对一个苹果进行基因改造。为了让苹果长得更快、产量更高、体积更大、外观更好看且更对称，苹果的 DNA 需要插入某种猪的基因。

苹果的 DNA 由字符集 $\{A, C, G, T\}$ 中的一系列字符表示。所需的猪基因也由该字符集中的字符组成。我们需要在苹果 DNA 的某些位置插入一些字符，使得改造后的序列在某处包含该猪基因（作为连续的子串）。为了让任务更具挑战性，插入字符 A、C、G、T 中的每一个都有其各自的代价。

请帮助这家跨国公司以最低的总体代价实现他们的目标。作为奖励，你将获得一吨他们生产的苹果。

输入格式

第一行包含一个长度为 $N$（$1 \le N \le 10\,000$）的字符串，表示苹果的 DNA。

第二行包含一个长度为 $M$（$1 \le M \le 5\,000$）的字符串，表示我们想要插入到苹果 DNA 中的猪基因。

两个字符串都仅由字符集 $\{A, C, G, T\}$ 中的字符组成。

第三行包含四个 $[0, 1000]$ 范围内的整数：依次为插入一个字符 A、C、G、T 的代价。

输出格式

输出的唯一一行应包含最小的总代价。

子任务

在占总分 80% 的测试数据中，$N$ 和 $M$ 将不超过 2000。

样例

输入样例 1

GTA
CAT
5 7 1 3

输出样例 1

10

输入样例 2

TATA
CACA
3 0 3 0

输出样例 2

3

输入样例 3

TCGCGAG
TGCAG
10 10 15 15

输出样例 3

25

说明

样例 1 澄清：一些可能的解决方案包括 G**CA**TA 和 GT**C**A**T**（插入的字符已加粗），第一种方案的代价为 $7 + 5$，第二种方案的代价为 $7 + 3$。