ژنتیک


  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

لئونارد در یک شرکت ژنتیکی استخدام شده که روی تغییر دنباله DNA گیاهان برای تولید محصولات بهتر کار می‌کند. یک ژن دنباله‌ای از حروف A، C، G و T‍ است.

در تحقیقات اخیر مشخص شده که اگر ژن سیب، شامل ژن tt به صورت یک زیر رشته‌ باشد، ماندگاری بیشتری خواهد داشت. برای رسیدن به این هدف می‌خواهیم تعدادی حرف در مکان‌های مشخصی از ژن سیب تزریق کنیم تا در نهایت ژن نهایی شامل ژن tt شود (ژن tt را به عنوان زیررشته داشته باشد).

تزریق هر یک از چهار کاراکتر هزینه‌ی خاصی دارد. وظیفه لئونارد یافتن مکان‌های تزریق ژن و کاراکتر‌های هر تزریق است به‌طوری که در نهایت هزینه کمینه شود. به او کمک کنید تا کمینه هزینه را محاسبه کند.

ورودی🔗

در خط اول یک رشته از nn کاراکتر داریم که ژن سیب را مشخص می کند. خط دوم شامل mm کاراکتر است که رشته‌ی tt را مشخص می کند. کاراکتر‌ها حروف انگلیسی بزرگ هستند. خط سوم شامل چهار عدد صحیح است که به ترتیبِ A، C، G و T‍ هزینه اضافه کردن هر کاراکتر را مشخص می کند.

1n10 0001 \le n \le 10\ 000

1m50001 \le m \le 5000

0ai10000 \le a_{i} \le 1000

خروجی🔗

در یک خط کمینه هزینه را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

TATA
CACA
3 0 3 0
Plain text

خروجی نمونه ۱🔗

3
Plain text

در این مثال هزینه‌ی اضافه کردن A و G برابر با ۳ و هزینه‌ی اضافه کردن C و T برابر با صفر است. لئونارد می‌تواند قبل از آخرین A حرف C و بعد از آن حرف‌های CA را اضافه کند و در مجموع ۳ واحد هزینه می‌کند.

ورودی نمونه ۲🔗

TCGCGAG
TGCAG
10 10 15 15
Plain text

خروجی نمونه ۲🔗

25
Plain text

در این مثال هزینه‌ی اضافه کردن A و C برابر با ۱۰ و هزینه‌ی اضافه کردن G و T برابر با ۱۵ است. لئونارد می‌تواند قبل از دومین G حرف T و بعد از آن حرف C را اضافه کند و به رشته‌ی ‍‍TCGCTGCAG برسد که TGCAG را به عنوان زیر رشته دارد و در مجموع ۲۵ واحد هزینه می‌کند.