Masala #0852

Rabin - Karp algoritmini urganish jarayonida qiziq bir narsa meni o'ylantirib qoldi. Sizga inglizcha harflardan iborat s satr beriladi. s satrni Pastki qator(substring)\(s[l...r](1 \leq l \leq r \leq \vert s \vert)\) larida yomon deb berilgan harflar soni ko'pi bilan k ta bo'lganlari sonini toping.
Agar 2 ta \(s[x...y] ≠ s[p...q]\) bo'lmasa ular har xil hisoblanadi, yani mano jihatidan bir xil bo'lmasligi kerak.

Birinchi qatorda s satr uzunligi 1500 dan oshmaydi.
Ikkinchi qatorda  26 ta harf uchun yaxshi yoki yomon ekanini belgilovchi '0' va '1' lardan iborat satr kiritiladi('0' bo'lsa yomon , '1' bo'lsa yaxshi).
Ohirgi qatorda k(\(0 \leq k \leq |s|\)) butun son kiritiladi.

Berilgan shartni qanoatlantiruvchi satrlar sonini toping.