Masala #0222

Xotira 512 MB Vaqt 2500 ms
14

Make-String

Sizga \(N\) uzunlikda \(S\) satr beriladi. Sizning vazifangiz ushbu satrdan yana bir nusxa tayyorlash, buning uchun sizga \(M\) ta \(L_i\) \((1 \le i \le M)\) satrchalar borligi aytiladi, bu satrchalar cheksiz ko`p. Siz \(S\) satrni \(M\) xil satrlar yordamida qayta yozishingiz kerak bunda \(L_i\) satr bilan \(L_j (1 \le i \le M, 1 \le j \le M,  i \space \text{va} \space j \space \text{bir xil bo`lishi mumkin})\) satrni faqat o`xshash harflarini ustma – ust qo`yish yordamida birlashtirishingiz yoki satrlarni ketma-ket joylashtirishingiz mumkin. Satrlarning tartibi buzilishiga ham ruxsat etilgan ammo satrlarni bo`laklash yoki teskarisiga o`girish mumkin emas.

Sizning vazifangiz \(S\) satrdan eng kam nechta belgini qayta tiklay olmasligingizni aniqlash. Unutmang siz hosil qiladigan satr \(N\) dan oshmasligi kerak!


Kiruvchi ma'lumotlar:

Birinchi qatorda \(N (1 \le N \le 3*10^5)\) butun son satr uzunligi.
Ikkinchi qatorda \(S\) satr beriladi.
Uchinchi qatorda \(M (1 \le M \le 5000)\) butun soni satrchalar soni
Keyingi \(M\) ta qatorda \(L_i (1 \le L_i \le 5000)\) satrchalar beriladi.
Barcha satrlardagi belgilar lotin kichik harflaridan iborat.


Chiquvchi ma'lumotlar:

Yagona butun son masala yechimini chop eting!


Misollar
# input.txt output.txt
1
18
abrakadabrakadabra  
3
abr
kada
kobra
3
2
18
abrakadabrakadabra  
3
abra
kada
kobra
0
Izoh:

1 – testda siz \(\text{abr+kada+\textcolor{red}{\text{a}}br+kada+\textcolor{red}{\text{a}}br}\) tartibda
natijada : \(\text{abr\{a\}kadabr\{a\}kadabr\{a\}}\)
Siz eng kamida 3 ta belgini hosil qilolmaysiz bular gulli qavs ichidagi \(a\) harflari

2 – testda siz \(\text{abra+kada+\textcolor{red}{a}bra+kada+\textcolor{red}{a}bra}\) tartibda
natijada : \(\text{abrakadabrakadabra}\)
Satrni to`liq hosil qilishingiz mumkin!

Izohlardagi qizil rangdagi harflar 2 marta yozilgan bunda ular ustma – ust qo`yilganini bildiradi.