### 问题描述 脱氧核糖核酸（英文 DeoxyriboNucleic Acid，缩写为 DNA）是生物细胞内含有的四种生物大分子之一核酸的一种。 DNA 携带有合成 RNA 和蛋白质所必需的遗传信息，是生物体发育和正常运作必不可少的生物大分子。 DNA 由两条脱氧核苷酸组成的大分子聚合物。脱氧核苷酸由碱基、脱氧核糖和磷酸构成。 其中碱基有 $4$ 种：腺嘌呤（A）、鸟嘌呤（G）、胸腺嘧啶（T）和胞嘧啶（C）。 根据碱基互补配对原则，**A 与 T 以两氢键配对，而 G 和 C 以三氢键配对**。 现给定两条脱氧核苷酸 $x, y$，你可以执行以下操作任意次直至 $x, y$ 匹配。 1. 翻转 $x$，代价为 $a$。 2. 翻转 $y$，代价为 $b$。 3. 对 $x$ 中的一个碱基使用魔法，代价为 $c$。 4. 对 $y$ 中的一个碱基使用魔法，代价为 $d$。 使用一次魔法可以实现以下功能之一： 1. 将一个 `A` 变成 `G`。 2. 将一个 `G` 变成 `T`。 3. 将一个 `T` 变成 `C`。 4. 将一个 `C` 变成 `A`。 这意味着将 `A` 变成 `T` 需要使用两次魔法。 若 $x, y$ 的匹配度不低于 $k$% 我们就称 $x, y$ 匹配。 求要使 $x, y$ 匹配的最小代价。 ### 输入格式 第一行一个字符串 $x$，表示第一条脱氧核苷酸。 第二行一个字符串 $y$，表示第二条脱氧核苷酸。 第三行五个正整数 $a, b, c, d, k$，分别表示操作 $1 \sim 4$ 的代价以及匹配要求。 ### 输出格式 输出一个整数，表示要使 $x, y$ 匹配的最小代价。 ### 样例输入 ``` AAAGGCCTTT TTTCCGGACC 1 2 3 4 90 ``` ### 样例输出 ``` 4 ``` ### 数据范围 对于 $100$% 的测试样例，$1 \leq len(x) = len(y) \leq 10^5$，$0 \leq a, b, c, d \leq 10^9$，$x, y$ 仅由 `AGCT` 构成，其中 $len(x)$ 表示 $x$ 的长度。 数据保证 $len(x) \times k$% 为整数。