Martian DNA

This problem is adapted from BalticOI 2018 Day 1 “Martian DNA”.

You are given a string s of length N over an alphabet of size \(|\Sigma| = K\). In addition, there are R requirements. Each requirement is specified by a character B and an integer Q, meaning that the chosen substring must contain the character B at least Q times.

Your task is to find the length of the shortest contiguous substring of s that satisfies all R requirements. If no such substring exists, output -1.

inputFormat

The input is given as follows:

N K R
s
B1 Q1
B2 Q2
... 
BR QR

Here,

• N is the length of the string.
• K is the size of the alphabet (\(|\Sigma| = K\)).
• R is the number of requirements.
• s is a string of length N consisting of characters from the given alphabet.
• Each of the next R lines contains a character B and an integer Q (separated by space), meaning that the substring must contain at least Q occurrences of B.

outputFormat

Output a single integer representing the length of the shortest substring of s that meets all the requirements. If no such substring exists, output -1.

sample

10 3 2
aabbbabaaa
a 4
b 3

8