Train Ticket Inspection

A train passes through N stations in order, including the first and last stations.

Before the train leaves the first station and after it arrives at the last station, there are no passengers on board. For each station, the number of passengers who get off and the number of passengers who get on are given.

Each passenger boards at one station, gets off at a later station, and does not ride the same train more than once.

A ticket inspector checks every passenger on board while the train travels from station 1 to station 2. After that, the inspector checks tickets every K station-to-station segments. In other words, for every integer a >= 0, if the segment from station a*K + 1 to station a*K + 2 exists, tickets are checked on that segment.

The actual assignment of passengers to boarding and alighting stations may vary as long as it is consistent with the given counts. Among all possible assignments, find the minimum and maximum possible number of passengers whose tickets are never checked.

The first line contains N and K. (2 <= N <= 1000, 1 <= K <= 1000)

Each of the next N lines contains two integers for one station, in station order: the number of passengers who get off the train and the number of passengers who get on the train. Every number is at least 0 and at most 1000.

Print two integers separated by a space: the minimum and maximum possible number of passengers whose tickets are never checked.