Jamshid Kazemi (who is known by the pseudonym Kamran Pouriai), has recently become a man and was released from prison. Jamshid after solving the great mystery of Snap; Within 70 days, he familiarized himself with modern programming technologies and quickly became a senior member of Snap due to his high talents. Snap wants to soon unveil its special service called Snap Lux on Bors Street. Before the unveiling, they have to solve a big problem and they have left it to Jamshid to solve this problem.

Bors Street, the center of Iran's stock market, is a long and horizontal street on one side of which you can stop the car. The place of the park has been marked by the municipality and next to this street in order and back to back
m
+
1
There are m+1 places to stop and park the car with 0
m
m is numbered from left to right. To park in some car parking spaces, the car in question must have an electronic tag of Electropark, which is very, very expensive. Since the length of the street is long, the municipality uses these places
n
n specifies an unsubscribed interval. interval
i
i indicates that all parking spaces with numbers between
l
i
l
i
​
 and
r
i
r
i
​
 (including both) need an Electropark label. They want to park their luxury cars on standby in some of these spaces on this street to provide optimal service to the people. Snap currently has two luxury cars in position 0 and
m
m is placed. In order for people to reach their cars quickly, no two adjacent luxury cars should be more than a distance apart
k
have k (in other words, in every
k
k consecutive parking spaces, there must be at least one luxury car). Therefore, they may need to put luxury cars in between these two positions; Therefore, in order to meet the customer's needs, SNAP first wants to place the least number of luxury cars in the required positions of Electropark, and then, among all the available methods of placing cars with the least number of cars in the required position of Electropark, use the lowest number of luxury cars. Help Jamshid solve this problem to prove himself to be the leader of his team.

input
In the first line of the input, three integers
n
n and
m
m and
k
k has arrived. Then in line
i
i of
n
n next line in order of two integers
l
i
l
i
​
 and
r
i
r
i
​
 has come The intervals in the input are in ascending order; that is
r
i
<
l
i
+
1
r
i
​
 <l
i+1
​
 .

It is guaranteed that no two intervals are shared and none contain positions 0 and
m
m are not

1
≤
n
≤
100

000
1≤n≤100 000
1
≤
k
≤
m
≤
1
0
9
1≤k≤m≤10
9

1
≤
l
i
≤
r
i
≤
m
-
1
1≤l
i
​
 ≤r
i
​
 ≤m−1

output
Print two numbers on the only output line. The first number is the minimum number of luxury cars that need electropark and the second number is the minimum number of luxury cars needed to be added. (Except for the cars parked in the 0 and
m
m are placed.)

Example
Sample entry 1
2 9 2
3 5
8 8
Plain text
Sample output 1
1 4
Plain text
In the optimal response for this example, cars are added in parking spaces 2, 4, 6, and 7, and space number 4 requires an electropark label.

Sample input 2
2 6 3
1 2
3 4
Plain text
Sample output 2
1 1
Plain text
In this example, the best case is to add a car in parking lot 3, which also needs an electropark label.  c++