Problem Description

                          ,▄▀▀▀▀▀▀▀▄
                       ▄P▀     ⁿ '  ▀▄ ,,,
                    ,Æ▀          ▌]▄▀▀    ╙▀▄
                  ,▀'         ' ▄▀▌  ▌    ═,▐▀N▄,
                ▄▀"           ²  '        ▌¬ ▄╘ `▀▄
            ▄Æ▀└¬ ▐ ²                              ▀▄
          ▄▀    *  ⌐             ╒  ┌ ," ²   ┌       ▀▄
        ▄▀  ┐           ` ',▄▄▄▄,". /  ,ⁿ, ,▄▄mm▄,     ▀N▄
      ,█¬⌐   ═       ,"▄Æ▀'      `▀▄╓⌐  ▐▄▀-   MÆ;▀▄ ▌▄   ▀▄
     Æ└ ═ ^   ∞  `  ▄Æ▀─∞           ▀▀▄▀         ═  ▀N,▄  ▄▀
    ▌╙⌐ + '   ∞  ▄Æ▀',,▄ .           ⌐`▀▄ ∞           `▀▄▀
    ▀▄ ¬ *└⌐ ▄P▀¬ ╓      ╓`,         `╓  ▀▄╛ ∞*          "█
 ▄▀▌▀▀▀█▀N▄P▀ `        ,           ╒w      ▀█ " +"╓ª┌      █
█▄ * ▄A▀▄▀r"⌐ "⌐    "           ,            ▀▄═ ▄═▐,▄,▄▄▄▀└
  ª-, ▄▀═ ^;" ;  ▌   "         ,*▄`           ╙█▄▄█▄▄▄    "
       └▀▀▄', ∞ `   ⌐¬  ,  ,   └  ²       ═ ,▄Æ▀ ▀▄▄▄▌▄█
           ▀▀▄▓▄▓▄▄▄▄▄  '      "⌐ ⌐ ,▄mM▀▀▀█▀▀▀▄▄▄
         ▐██▌  +  -   ▐▀▀▀═MM∞∞∞MP▀▀ , "╒▀'`╤]▄▄▄A▀ 

This Kata is the second in the Do a Smart Guess collection series. If you haven't solved the first Kata, check it out: Find Out the Number of Gold Coins!.

After dealing with the guardian in the last Kata, you and your friends continue the RPG campaign, and now you encounter a mysterious wizard.

The wizard promises to give you a legendary magic item, but for that you must guess the number of grains of magic sand that are in the wizard's bag. For this, he gives the following tips:

• $11$. If the number of grains were divided between $m_{1}m\_1$ people, $a_{1}a\_1$ grains would be left.

• $22$. If the number of grains were divided between $m_{2}m\_2$ people, $a_{2}a\_2$ grains would be left.

• $33$. If the number of grains were divided between $m_{3}m\_3$ people, $a_{3}a\_3$ grains would be left.

  $\backslash vdots$

• $NN$. If the number of grains were divided between $m_{N}m\_N$ people, $a_{N}a\_N$ grains would be left.

Of course $m_{i}m\_i$ is always a positive integer and $0\le a_i<m_{i}0\; \backslash leq\; a\_i\; \backslash lt\; m\_i$.

The wizard doesn't seem very trustworthy, so he might be trying to trick you, and there aren't any number of grains of sand that satisfy the conditions he gives.

Your Task

Given the wizard information, write the function number_of_grains that returns the minimum number of grains of magic sand in the wizard's bag.

This function receives information in the form of a list of tuples:

[(a1, m1), (a2, m2), ... , (aN, mN)]

If the wizard is trying to trick you, and there is no number of grains of sand that satisfies the given information, your function should return None.

Example

Suppose that the tips from the wizard are:

• $11$. If the number of grains were divided between $44$ people, $33$ grains would be left.

• $22$. If the number of grains were divided between $66$ people, $11$ grain would be left.

So, the minimum number of grains of sand is 7, because 7 is the smallest number that when divided by 4 has remainder 3 and when divided by 6 has remainder 1. Thus:

number_of_grains([(3, 4), (1, 6)]) = 7

Suppose the wizard gave one more tip:

• $33$. If the number of grains were divided between $22$ people, no grain would be left.

In this case, the problem has no solution, because there is no number that divided by 2 has a remainder of 0 (that is, an even number) that when divided by 4 has a remainder of 3. Thus:

number_of_grains([(3, 4), (1, 6), (0, 2)]) = None

Performance Requirements

Consider that the maximum input length will be 15 (that is, the wizard will give at most 15 tips, $1\le N\le 151\; \backslash leq\; N\; \backslash leq\; 15$).

The $m_{i}m\_i$ values will be always less than $10^{20}10^\{20\}$, so the minimum number of grains of sand can be quite large. However, that shouldn't be a problem for your algorithm.

Have fun coding and please don't forget to vote and rank this kata! :-)