System of Remainders

Difficulty: 2200 4000 ms 128 MB

number-theory

Find the smallest non-negative x satisfying x ≡ r_i (mod m_i) for all i. The moduli are NOT necessarily coprime, so a solution may not exist — print −1 then.

Input: the first line has K; each of the next K lines has r_i and m_i.

Output: the smallest non-negative solution, or −1.

Constraints:

• 1 ≤ K ≤ 10
• 1 ≤ m_i ≤ 10⁶
• 0 ≤ r_i < m_i

Sample Tests

2
2 3
3 5

8

2
0 4
2 6

8

Read the Editorial