Day of Abundance
In the port of Greenland, situated on the shores of the Multicolored Sea, ships occasionally dock, bringing various goods that are sold in the village's shops. There are N ships, each docking at the port with a specific frequency.
Life is challenging for the villagers on days when no ships arrive. Not only do they have to navigate through barbed wire and minefields to reach the store, risking falling into a sewer manhole, but the store itself is empty. Traveling to a more civilized place with a market or supermarket is out of the question due to the exorbitant cost of minibuses, which are packed tightly, not with people, but like sardines.
Imagine the immense joy of the "Greenlanders" when at least one ship docks at the port, as it means products will finally be available in the stores. However, the joy is even greater on a day when all N ships arrive at the port simultaneously. Such a day is celebrated as a day of abundance.
The residents of Greenland request your help to write a program that determines how long they must wait for this special day.
Input
The first line of the input specifies the number of ships N (1 ≤ N ≤ 100). The following N lines each contain two natural numbers: the first day a particular ship arrives at the port, and the interval in days after which it will arrive again. All numbers do not exceed 10^9.
Output
Output a single line with the number of the first day when all ships will be at the port together. If no such day exists, output -1. You can assume that if such a day exists, its number does not exceed 2·10^9.