15862번 - Martian DNA 서브태스크다국어

As you are probably aware, human DNA can be represented as a long string over an alphabet of size four (A, C, G, T), where each symbol represents a distinct nucleobase (respectively; adenine, cytosine, guanine, and thymine).

For martians, however, things are a bit different; research conducted on the latest martian captured by NASA revealed that martian DNA consists of a whopping K distinct nucleobases! Martian DNA may thus be represented as a string over an alphabet of size K.

Now, a certain research group interested in exploiting martian DNA in artificial intelligence applications has requested to get a single consecutive piece of a martian DNA string. For R of the nucleobases, they have specified a minimum quantity of how many they need of that particular nucleobase to be present in their sample.

You are interested in finding the shortest substring of the DNA which satisfies their requirements.

The first line contains three integers N, K, and R, denoting the total length of the martian DNA, the alphabet size, and the number of nucleobases for which the researchers have a minimum quantity requirement, respectively. They obey 1 ≤ R ≤ K ≤ N.

The second line contains N space-separated integers: the complete martian DNA string. The i-th of these integers, D_i, indicates what nucleobase is in the i-th position of the DNA string. Nucleobases are 0-indexed, i.e. 0 ≤ D_i < K. Each nucleobase will occur at least once in the DNA string.

Each of the following R lines contains two integers B and Q representing a nucleobase and its mimimum required quantity, respectively (0 ≤ B < K, 1 ≤ Q ≤ N). No nucleobase will be listed more than once in these R lines.

Output a single integer, the length of the shortest consecutive substring of the DNA that satisfies the researchers’ requirements. If no such substring exists, output “impossible”.

• 1 ≤ N ≤ 100
• R ≤ 10

• 1 ≤ N ≤ 4000
• R ≤ 10

• 1 ≤ N ≤ 200000
• R ≤ 10

• 1 ≤ N ≤ 200000

In the first sample, there are three substrings of length 2 that contain one each of nucleobases 0 and 1 (namely “0 1”, “1 0” and “0 1”), but no substrings of length 1. Thus the shortest length is 2.

In the second sample, the (unique) optimal substring is “1 3 2 0 1 2 0”.

In the third sample, there aren’t enough nucleobases of type 0.