resturi

Se dă un număr natural $K$ şi numerele naturale $p_1, p_2, …, p_K, r_1, r_2, ... , r_K$, unde $p_1, ... , p_K$ sunt numere prime diferite două câte două şi $0 \leq r_i < p_i$, pentru orice $i$ de la $1$ la $K$. Spunem că un număr $X$ este liber de resturi, dacă restul împărţirii lui $X$ la $p_i$ este diferit de $r_i$, pentru orice $i$ de la $1$ la $K$. Considerăm şirul sortat al numerelor naturale libere de resturi.

Cerinţă

Să se determine al $N$-lea element al şirului.

Date de intrare

Fişierul resturi.in conţine pe prima linie numerele $K$ şi $N$, separate printr-un spaţiu. Următoarele $K$ linii conţin perechi de numere $p_i, r_i$, separate printr-un spaţiu.

Date de ieşire

Fişierul resturi.out conţine pe prima linie un singur număr $M$, reprezentând al $N$-lea număr din şirul considerat.

Restricţii şi precizări

• $0 \leq K \leq 10$
• $1 \leq N \leq 2 \ 000 \ 000 \ 000$ (două miliarde)
• Şirul considerat este indexat începând de la $1$.
• Se garantează că rezultatul va fi mai mic decât $10 \ 000 \ 000 \ 000$ (zece miliarde). Programatorii în C++ pot folosi tipul de date long long, iar cei în Pascal tipul int64.

Exemplul 1

resturi.in

3 6
2 1
3 2
5 2

resturi.out

18

Explicație

În acest caz, şirul considerat este: $0, 4, 6, 10, 16, 18, 24, ...$

Exemplul 2

resturi.in

4 16
3 2
17 9
7 1
23 0

resturi.out

30

Explicație

În acest caz, şirul considerat este: $3, 4, 6, 7, 10, 12, 13, 16, 18, 19, 21, 24, 25, 27, 28, 30, 31, ...$