1989. Erratic Sleep Habits

单点时限: 2.0 sec

内存限制: 256 MB

Peter is a person with erratic sleep habits. He goes to sleep at twelve o’clock every midnight. He gets up just after one hour of sleep on some days; he may even sleep for twenty-three hours on other days.His sleeping duration changes in a cycle, where he always sleeps for only one hour on the first day of the cycle.

Unfortunately, he has some job interviews this month. No doubt he wants to be in time for them. He can take anhydrous caffeine to reset his sleeping cycle to the beginning of the cycle anytime. Then he will wake up after one hour of sleep when he takes caffeine. But of course he wants to avoid taking caffeine as possible, since it may affect his health and accordingly his very important job interviews.

Your task is to write a program that reports the minimum amount of caffeine required for Peter to attend all his interviews without being late, where the information about the cycle and the schedule of his interviews are given. The time for move to the place of each interview should be considered negligible.


The input is given in the following format:


t1 t2 . . . tT


D1 M1

D2 M2

. . .


T is the length of the cycle (1 <= T <= 30); ti (for 1 <= i <= T) is the amount of sleep on the i-th day of the cycle, given in hours (1 <= ti <= 23); N is the number of interviews (1 <= N <= 100); Dj (for 1 <= j <= N) is the day of the j-th interview (1 <= Dj <= 100); Mj (for 1 <= j <= N) is the hour when the j-th interview starts (1 <= Mj <= 23).

The numbers in the input are all integers. t1 is always 1 as stated above. The day indicated by 1 is the first day in the cycle of Peter’s sleep.


Print the minimum number of times Peter needs to take anhydrous caffeine.


1 23
1 1
2 1
3 1

24 人解决,40 人已尝试。

29 份提交通过,共有 182 份提交。

5.7 EMB 奖励。

创建: 11 年,4 月前.

修改: 4 年前.

最后提交: 10 月前.

来源: Japan