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
fawad: 2020-06-30 03:09:51

Thank you @arftdipto for test cases. 1 wa, then saw test cases, made changes in code, and then ac!!!

arftdipto: 2020-02-13 15:02:23

10
aaxbcxyabc
3
1 a
1 b
1 c
##########
10
aaxbcxyabc
3
2 a
1 b
1 c

Last edit: 2020-02-13 15:02:52
raunak__singha: 2017-05-15 15:01:59

fast I/O with O(n) AC in 0.00

krototype: 2016-07-24 18:46:09

someone please provide any good testcase

Vignesh Manoharan: 2014-11-26 21:28:09

block refers to substring
why cant the problem just say substring huh :-|

ping_of_death: 2014-10-24 04:40:22

What is a block of tile in the question please explain.

Jacob Plachta: 2014-10-24 00:15:52

Apparently, the block must contain *at least* the required number of each plant type, not exactly.

Andy: Edited description for clarity, thanks!

Last edit: 2014-10-22 09:18:05

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