NPC2014F  Field
Andy is a successful farmer. He has a field sized 1 x N tiles, where each tile can be planted a plant. Andy has 26 kind of plants, which is represented by the letter 'a'  'z'.
Each month Andy has to pay tax to the government. The government in his place is very picky. He wants the tax in the form of a block of tiles. He also demands that the block must contain at least Xi number of plant type Yi. A block of tiles is all the tile from range a to b. To minimize the loss, Andy will pay in the smallest block possible. Help Andy to find the length of the smallest block to satisfy the government.
Input
Starts with a number N. The next line is a string of length N containing the letter 'a' to 'z'. The next line is a number K, and for the next K lines are the Xi and Yi, number and type of plants that must be fulfilled.
Output
Minimum length of block to pay the tax. If Andy can't pay the tax, output "Andy rapopo".
Sample Input 1
5
aabac
3
1 a
1 b
1 c
Sample Output 1
3
Sample Input 2
5
aabac
3
1 a
1 b
2 c
Sample Output 2
Andy rapopo
Constraint
 1 ≤ N ≤ 100000
 1 ≤ K ≤ 26
 1 ≤ X ≤ 100000
 Yi is a character from 'a' to 'z'
 Each Yi type will not appear more than once
Time limit is very strict, some language might not be able to pass.
hide comments
raunak__singha:
20170515 15:01:59
fast I/O with O(n) AC in 0.00


krototype:
20160724 18:46:09
someone please provide any good testcase 

Vignesh Manoharan:
20141126 21:28:09
block refers to substring


ping_of_death:
20141024 04:40:22
What is a block of tile in the question please explain. 

Jacob Plachta:
20141024 00:15:52
Apparently, the block must contain *at least* the required number of each plant type, not exactly.

Added by:  Andy 
Date:  20141021 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  NPC Schematics 2014 