提示: 欢迎访问OurACM平台。
Problem 1794 Top Shooter

Accept: 82    Submit: 284
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Since the Border War in 1962, Both China and India abide by the principle of no-expansion of military power, but India's recent actions are obviously going against this principle. Indian Prime Minister Singh delivered a speech in Congress, said that "regardless of face of China or other countries, India will, by all means to ensure the territorial integrity, national unity and security." At the same time, India increases more than sixty thousand troops to the southern Tibetan, including the construction of five airports and advanced landing field. Obviously this behavior undermines the trust between the two countries. Aggressive as a result of India, China announced the establishment of commando in Tibet!

The commando consists of N snipers. Messages show that Indian will send airborne to our Border. Our Army organizes the commando ambushing in the mountains. A sniper can only hit the target in his field of vision. And will not be able to hit the target outside his field of vision As the captain of the commando, how will you show your talent to win the battle?

Input

The input consists of several test cases. The first line of each case contains two integers N, M (1<=N<=50, 1<=M<=1000), N representing the number of snipers, M representing the number of airborne. The next line contains N numbers (Hi,(1<=i<=N)), representing each sniper’s field of vision.(the field of vision Hi means that the sniper can only see the target higher than or equal to Hi meters), The next M lines contain a pair of integers(Ai,Hi) each, representing the airborne i (1<=i<=M) begin to fall at the moment Ai, and from the height Hi,(1<=Ai<=100,1<=Hi<=500). We assume that each airborne falls one meter per second, a sniper can only hit one target per second.

Output

Output the maximum number of airborne the sniper team can hit.

Sample Input

2 5 1 9 1 2 1 2 1 2 2 2 2 4

Sample Output

4

Source

Multi-School Training Contest - FOJ Site #7

Submit  Back  Status  Discuss