87 - ZOJ Monthly, February 2010 - B
As all you know, MM loves cookies very much and now she's going to make another cookie choice!
There is a sequence of N cookies while there may be K different kinds of cookies.
MM wants to choose a continuous subsequence of cookies to eat (the subsequence may be empty), while for each kind of cookie, there are minimum and maximum numbers MM want to choose.
But DD wants to minimize the length of chosen continuous subsequence (for his poor wallet). You are to find the shortest continuous sequences that satisfy MM's requirement.
Formally speaking, define the cookie sequence as Ci (1<=i<=N, 1<=Ci<=K), where Ci is the kind of the ithe cookie, and the chosen continuous subsequence has Mi cookies of kind i. Mi must satisfy Ai<=Mi<=Bi. While Ai and Bi are given miminum and maximum numbers of kind i to choose.Input
About 20 test cases, seperated by blank line.
First line of each case is two integers N (1<=N<=400000) and K (1<=K<2048). The second line is N numbers of sequence C. The following K lines, the ith line has two numbers Ai and Bi.
All numbers are integers.Output
For each test case, output the minimum length of chosen continuous subsequence.
If no answer, output -1.Sample Input
5 2 1 2 2 2 1 2 4 1 3 7 2 1 2 1 2 1 2 1 3 4 0 1Sample Output
Author: CUI, Tianyi
Source: ZOJ Monthly, February 2010