Se dă un număr natural K şi numerele naturale p1, p2, …, pK, r1, r2, …, rK, unde p1, …, pK sunt numere prime diferite două câte două şi 0 <= ri < pi, 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 pi este diferit de ri, 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 doua numere pi ri, 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
• 0 <= K <= 10
• 1 <= N <= 2000000000 (două miliarde)
• Şirul considerat este indexat începând de la 1.
• Se garantează că rezultatul va fi mai mic decât 10000000000 (zece miliarde). Programatorii în C++ pot folosi tipul de date long long, iar cei în Pascal tipul int64.
Exemple
resturi.in
resturi.out
Explicaţii
3 6
2 1
3 2
5 2
18
În acest caz, şirul considerat este: 0, 4, 6, 10, 16, 18, 24, …
4 16
3 2
17 9
7 1
23 0
30
În acest caz, şirul considerat este: 3, 4, 6, 7, 10, 12, 13, 16, 18, 19, 21, 24, 25, 27, 28, 30, 31, …