기차표 검사

총 N개의 역을 순서대로 지나는 기차가 있다. 첫 번째 역과 마지막 역도 역의 수에 포함한다.

기차가 첫 번째 역을 출발하기 전과 마지막 역에 도착한 뒤에는 기차에 승객이 없다. 각 역에서 기차에서 내리는 승객 수와 기차에 타는 승객 수가 주어진다.

각 승객은 어떤 역에서 기차를 타고, 그보다 뒤에 있는 한 역에서 내린다. 같은 승객이 같은 기차를 두 번 이상 타지는 않는다.

검표원은 기차가 1번째 역에서 2번째 역으로 이동하는 동안, 그때 기차에 타고 있는 모든 승객의 표를 검사한다. 이후에는 기차가 역 사이 구간을 K개 지날 때마다 다시 표를 검사한다. 즉, 정수 a >= 0에 대해 a*K + 1번째 역에서 a*K + 2번째 역으로 이동하는 구간이 존재하면, 그 구간에서 표를 검사한다.

승객들이 실제로 어느 역에서 타고 내렸는지는 주어진 승하차 인원과 모순되지 않는 한 여러 가지일 수 있다. 가능한 모든 배정 중에서 표를 한 번도 검사받지 않는 승객 수의 최솟값과 최댓값을 구하라.

첫째 줄에 N과 K가 주어진다. (2 <= N <= 1000, 1 <= K <= 1000)

다음 N개 줄에는 역 순서대로, 각 역에서 기차에서 내리는 승객 수와 기차에 타는 승객 수가 공백으로 구분되어 주어진다. 모든 수는 0 이상 1000 이하이다.

첫째 줄에 표를 한 번도 검사받지 않는 승객 수의 최솟값과 최댓값을 공백으로 구분해 출력한다.