+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- لئونارد در یک شرکت ژنتیکی استخدام شده که روی تغییر دنباله *DNA* گیاهان برای تولید محصولات بهتر کار می‌کند. یک ژن دنباله‌ای از حروف `A`، `C`، `G` و `T‍` است. در تحقیقات اخیر مشخص شده که اگر ژن سیب، شامل ژن $t$ به صورت یک زیر رشته‌ باشد، ماندگاری بیشتری خواهد داشت. برای رسیدن به این هدف می‌خواهیم تعدادی حرف در مکان‌های مشخصی از ژن سیب تزریق کنیم تا در نهایت ژن نهایی شامل ژن $t$ شود (ژن $t$ را به عنوان زیررشته داشته باشد). تزریق هر یک از چهار کاراکتر هزینه‌ی خاصی دارد. وظیفه لئونارد یافتن مکان‌های تزریق ژن و کاراکتر‌های هر تزریق است به‌طوری که در نهایت هزینه کمینه شود. به او کمک کنید تا کمینه هزینه را محاسبه کند. # ورودی در خط اول یک رشته از $n$ کاراکتر داریم که ژن سیب را مشخص می کند. خط دوم شامل $m$ کاراکتر است که رشته‌ی $t$ را مشخص می کند. کاراکتر‌ها حروف انگلیسی بزرگ هستند. خط سوم شامل چهار عدد صحیح است که به ترتیبِ `A`، `C`، `G` و `T‍` هزینه اضافه کردن هر کاراکتر را مشخص می کند. $$1 \le n \le 10\ 000$$ $$1 \le m \le 5000$$ $$0 \le a_{i} \le 1000$$ # خروجی در یک خط کمینه هزینه را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` TATA CACA 3 0 3 0 ``` ## خروجی نمونه ۱ ``` 3 ``` در این مثال هزینه‌ی اضافه کردن `A` و `G` برابر با ۳ و هزینه‌ی اضافه کردن `C` و `T` برابر با صفر است. لئونارد می‌تواند قبل از آخرین `A` حرف `C` و بعد از آن حرف‌های `CA` را اضافه کند و در مجموع ۳ واحد هزینه می‌کند. ## ورودی نمونه ۲ ``` TCGCGAG TGCAG 10 10 15 15 ``` ## خروجی نمونه ۲ ``` 25 ``` در این مثال هزینه‌ی اضافه کردن `A` و `C` برابر با ۱۰ و هزینه‌ی اضافه کردن `G` و `T` برابر با ۱۵ است. لئونارد می‌تواند قبل از دومین `G` حرف `T` و بعد از آن حرف `C` را اضافه کند و به رشته‌ی ‍‍`TCGCTGCAG` برسد که `TGCAG` را به عنوان زیر رشته دارد و در مجموع ۲۵ واحد هزینه می‌کند.

حل سؤال در بانک سؤالات