Resturi2

resturi2

== include(page="template/taskheader" task_id="resturi2") ==

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 <= 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.

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 <= 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.

Să se determine al $N$-lea element al şirului.
h2. 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.

Fişierul de intrare $resturi2.in$ ...

h2. 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.

În fişierul de ieşire $resturi2.out$ ...

h2. Restricţii

* $0 ≤ K ≤ 10$
* $1 ≤ N ≤ 2 000 000 000$
* Ş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).

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. resturi2.in |_. resturi2.out |

| 3 6
2 1
3 2
5 2
| 18
|
 
În acest caz, şirul considerat este: 3, 4, 6, 7, 10, 12, 13, 16, 18, 19, 21, 24, 25, 27, 28, 30, 31, …
 
table(example). |_. resturi2.in |_. resturi2.out |
| 4 16
3 2
17 9
7 1
23 0
| 30

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

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

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="resturi2") ==