Problem F
Hotels

The beautiful city of Leiden draws more and more tourists
every year. Opposite the famous Hilbert Hotel, located near the
city border, a competing chain is building a hotel in a project
nicknamed Lodgings In A Colossal Skyscraper (LIACS).
As you may know, the Hilbert Hotel has an infinite number of
rooms. Guests at the Hilbert have been complaining that it
takes them forever to reach their room, so the competing hotel
chain decided that LIACS will only have finitely many rooms.
Nevertheless, LIACS will become a colossal skyscraper
consisting of many many floors, precisely
The floors will be connected by both elevators and
stairways. Fire regulations demand that it must be possible to
reach the ground floor using only the stairs, so there is a
stairway going from the top floor all the way down to the
ground floor (with a door on every floor in between). On the
other hand, the elevators can only pick up people on so many
floors before they are full, so the project manager decided
that no elevator should stop on every floor. More precisely,
the
The guests do not mind taking the elevator or changing elevators many times in a row, but they do not like taking the stairs. The LIACS project manager has no idea whether his planned elevators provide acceptable coverage, so he asked you to calculate how many flights of stairs his guests have to take in order to get to their room, assuming that their room is situated on the worst possible floor. Guests always enter the hotel on the ground floor. Note that guests may alternately take the stairs and take the elevators in order to reach their room, as not every elevator stops at the ground floor. (See sample input below.)
Input
The input starts with a line containing an integer
-
One line with two space-separated integers
and , denoting the number of floors and elevators, respectively. These satisfy and . The floors are numbered from to , where is the ground floor and is the top floor. (This is quite common in the Netherlands, whereas in other countries the ground floor is sometimes numbered instead of .) -
lines, each containing two space-separated integers and satisfying and . These denote the remainder and the modulus for every elevator. It is guaranteed that every elevator stops on at least and at most floors.
Output
For each test case, output one line with two integers
-
is the number of stairs a guest has to take if his room is located on the worst possible floor, -
is the number of the worst possible floor. If multiple floors are equally bad, output the one closest to the ground floor.
In the second test case, the top floor is numbered
Sample Input 1 | Sample Output 1 |
---|---|
5 21 3 0 3 1 3 2 3 21 2 0 3 1 3 15 2 2 3 1 4 10 0 99 3 0 2 1 2 0 3 |
1 1 2 20 2 3 9 9 0 0 |