Description

在經過一年的大學生活摧殘後,我發覺寫作業好難,寫題敘更難

不過活在2023年有個好處,那就是可以叫 ChatGPT 幫你把報告打好

然而這樣的缺點是 ChatGPT 經常有錯誤

因為你完全沒有在上課,所以你不知道 ChatGPT 寫的是不是對的

於是為了拿到分數,你決定讓 ChatGPT 生成一份報告後,再跟同學拿了一份他寫好的報告

你決定在 ChatGPT 生成好的報告中加上一些廢話,讓你的報告盡可能地貼近你同學的報告

然而寫太多廢話會讓你的報告看起來很奇怪又降低分數,於是你決定只加剛剛好的廢話讓你的報告跟你同學的一樣長

同時又不能讓你的報告跟你的同學的差太多(雖然太接近會被抓抄襲,不過加上那些廢話後助教應該抓不到)

具體來說,ChatGPT 寫的報告會是一個字串 $A$,同學的報告則是字串 $B$,其中 $|A| < |B|$。

你可以在 $A$ 當中填入一些 - 字元使 $|A| = |B|$,每次可以填入連續 $k$ 個這樣的字元,花費 $a+bk$。
而完成後的字串每有一個 $A_i \neq B_i$ 且 $A_i \neq$ -,都會再花費 $c$。

請最小化花費

然後剛剛那個題敘好難懂所以我叫 ChatGPT 再幫我寫ㄌ一份

(我prompt打錯ㄌ,請不要參考圖內的題敘)

曾經有一個古老的城鎮,名叫字串城。這座城市以其奇特的建築和獨特的居民而聞名。城市的居民都是由字母所組成的字串,每個人都被賦予了一個特殊的名字。

在字串城的某一天,城市的魔法師提出了一個有趣的挑戰給城裡的居民。他們必須將自己的名字轉變成另一個居民的名字,但轉換過程中只能進行一項操作:在自己的名字中插入連續的 - 字元。

城市裡的居民都很興奮地接受了這個挑戰,每個人都有一個目標名字,希望能以最小的花費將自己的名字轉變成目標名字。然而,城市魔法師並沒有透露這個挑戰的具體花費方式,而是給予了一個數學模型。

在字串城的轉換過程中,每插入一段連續的 - 字元,都需要支付一筆費用。而這個費用由兩個參數決定:$a$ 和 $b$。插入 $k$ 個 - 字元的費用為 $a + bk$ 元。

此外,當最終轉換後的字串中的對應字元 $A_i$ 不等於 $B_i$ 且 $A_i$ 並不是 - 時,還需要支付額外的費用 $c$ 元。這表示,每當兩個字串中的對應位置有不同的字元時,都需要支付 $c$ 元。

Input Format

第一行為一個字串 $A$

第二行為一個字串 $B$

第三行有三個正整數 $a, b, c$

$0 \leq a, b, c \leq 10 ^ 6$

$0 < |A| < |B| \leq 3000$

字串均由小寫英文字母組成

Output Format

輸出一個正整數表示最小花費

Sample Input 1

ckefgisc
weareckefgisctwentyeighth
1 2 3

Sample Output 1

36

Sample Input 2

ad
aadd
1 1 1

Sample Output 2

3

Sample Input 3

abcd
eebeed
100 1 1

Sample Output 3

105

Hints

以下是 3 個 Sample 的最佳填入法範例
1. -----ckefgisc------------
2. a--d
3. --abcd

Subtasks

No. Testdata Range Score

TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

100.0% (5/5)

Tags

Problem Source

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536
1 1000 262144 65536
2 1000 262144 65536
3 1000 262144 65536
4 1000 262144 65536
5 1000 262144 65536
6 1000 262144 65536
7 1000 262144 65536
8 1000 262144 65536
9 1000 262144 65536
10 1000 262144 65536
11 1000 262144 65536
12 1000 262144 65536
13 1000 262144 65536
14 1000 262144 65536
15 1000 262144 65536
16 1000 262144 65536
17 1000 262144 65536
18 1000 262144 65536
19 1000 262144 65536
20 1000 262144 65536
21 1000 262144 65536
22 1000 262144 65536
23 1000 262144 65536
24 1000 262144 65536
25 1000 262144 65536
26 1000 262144 65536
27 1000 262144 65536
28 1000 262144 65536
29 1000 262144 65536
30 1000 262144 65536
31 1000 262144 65536