Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3297
Cookie Choice II

Time Limit: 4 Seconds      Memory Limit: 32768 KB

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.


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.


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 1
Sample Output

Author: CUI, Tianyi
Source: ZOJ Monthly, February 2010
Submit    Status