kontrola

문제

A train is operating on a line that consists of N stops (including the first and last stops). 

The train is empty in the beginning and in the end, and for each stop we know the number of passengers that leave the train and the number of passengers that enter the train. Each passenger is traveling for some number of stops and the same passenger never boards the same train more than once. 

There is a ticket inspector in the train. He walks through the entire train between the first and second stops and inspects the tickets of all passengers currently aboard. After that, the inspector inspects tickets again after every K stops (hence he inspects the ticket between stops a*K+1 and a*K+2 for each integer a). It is therefore possible that some passengers enter and leave the train with their tickets never inspected. 

Write a program that finds the minimum and maximum possible number of such passengers. 

입력

The first line of input contains two integers N and K, 2 ≤ N ≤ 1000, 1 ≤ K ≤ 1000. 

Each of the next N lines contains two integers – the number of passengers that leave and the number of passengers that enter on that particular stop (from the first to the last stop). These numbers will be greater than or equal to 0 and no greater than 1000.

출력

The first and only line of output should contain two integers – the minimum and maximum numbers from the task description. 

3 2
0 5
4 2
3 0

2 2

4 2
0 5
0 5
3 0
7 0

0 3

6 2
0 10
5 3
6 4
2 8
8 1
5 0

5 11