The Chinese Remainder Puzzle

An old puzzle from China asks: there is a pile of coins. Counted in threes, 2 are left over. Counted in fives, 3 are left over. Counted in sevens, 2 are left over. How many coins are there? The smallest answer is 23.

Write smallest_solution(rules) that takes a list of pairs (remainder, modulus) and returns the smallest whole number x >= 0 with x % modulus == remainder for every pair. If no number meets all the rules, return -1.

The moduli can share factors, so some lists of rules have no answer at all.

Examples

smallest_solution([(2, 3), (3, 5), (2, 7)])    # returns 23
smallest_solution([(1, 4), (3, 6)])            # returns 9
smallest_solution([(1, 4), (2, 6)])            # returns -1

In the last one, x % 4 == 1 makes x odd but x % 6 == 2 makes it even.

Constraints

• 1 <= len(rules) <= 20
• 1 <= modulus <= 10^9 and 0 <= remainder < modulus
• The answer can be far bigger than 10^18, so counting upwards from 0 is hopeless.