Problem Statement
You are analysing a monkey which is sitting on a line, it is at point on the line and is throwing poo left and right onto other points.
You wish to know how much poo the monkey is throwing, so you have set up buckets along the line, which cover some sections of the line, the bucket covers all points from to inclusive.
You are going to go in your rover to pick up the poo, but you need to know how much poo the buckets have caught. To measure this, you set up a radar on the monkey which outputs the distance from the monkey that the monkey threw the poo, however you forgot to measure weather the poo goes left or right! This means you don't know if it lands in one of your buckets or not.
Output the maximum and the minimum amount of poo you could have gotten in the buckets given the information from the radar.
Input Format
Your first line will contain three space-separated integers , and , representing the number of radar measurements, the point of the monkey and the number of buckets you set up respectively.
Your next line will contain non-negative integers, the of which represents the distance that the piece of poo the monkey threw travelled.
Your next lines will contain two integers each, the of which will contain and which is the interval the bucket covers.
Output Format
You should output a single line containing two space-separated integers, the first being the maximum amount of poo that could have been collected in the buckets and the second being the minimum amount of poo that could have been collected in the buckets.
Constraints
Sample Cases
Input 1
10 10 3
0 1 2 3 4 5 6 7 8 9
1 4
18 20
7 10
Output 1
8 3
Explanation 1
Notice the poos that are thrown a distance , and must land in a bucket (for example the poo thrown a distance will land in the bucket as it will land on point ), therefore at least poos will be caught.
In a similar way, buckets , , , , , , and may or may not land in a bucket depending on if they're thrown left or right, therefore there is a maximum of poos that can be caught potentially.
Input 2
3 10 2
5 9 3
1 2
1 3
Output 2
1 0
Input 3
1 100000 1
99999
1 1
Output 3
1 0
Template
n, x, k = map(int, input().split())
poo_distances = list(map(int, input().split()))
buckets = [tuple(map(int, input().split())) for _ in range(k)] # list of tuples [(l_1, r_1), (l_2, r_2), ...]
# print your output
Comments