pinball

La un concurs de pinball, în 2026, s-a întâmplat ceva inedit. Cei $n$ participanți la concurs au obținut punctajele $v_1, v_2, \dots, v_n$, numere naturale nenule. Pe lângă obișnuitele aplauze, au fost recompensați la finalul concursului cu bomboane. O persoană care a obținut punctajul $x$ a primit un număr de bomboane egal cu numărul de divizori naturali ai lui $x$.

Cerințe

1. Știind că la începutul concursului, bugetul a fost de $b$ bomboane, să se determine numărul $nr$ de bomboane care au rămas după concurs.
2. Să se determine ce punctaj $P$ cu proprietatea $1 \le P \le 6\ 000\ 000\ 000$ ar trebui să obțină al $(n + 1)$-lea participant, astfel încât să nu mai rămână nicio bomboană.

Date de intrare

Fișierul de intrare pinball.in conține pe prima linie trei numere naturale nenule $C$, $n$ și $b$, separate prin câte un spațiu, ce reprezintă cerința $C$ ($1$ sau $2$) care trebuie rezolvată, numărul $n$ de participanți la concurs, respectiv bugetul de $b$ bomboane. Pe a doua linie, fișierul conține $n$ numere naturale $v_1, v_2, \dots, v_n$, separate prin câte un spațiu, reprezentând punctajele participanților.

Date de ieșire

Fișierul de ieșire pinball.out conține un număr natural nenul ce reprezintă răspunsul la cerința $1$ dacă $C = 1$, respectiv răspunsul la cerința $2$ dacă $C = 2$.

Restricții și precizări

• $1 \le n \le 300\ 000$
• $1 \le b \le 100\ 000\ 000$
• $1 \le v_i \le 2\ 000\ 000$, $1 \le i \le n$
• pentru ambele cerințe se garantează că $1 \le nr \le 800$ și $nr$ nu este divizibil cu niciun număr prim mai mare decât $7$
• pentru $C = 2$ se acceptă orice soluție corectă $P \le 6\ 000\ 000\ 000$ pentru punctaj maxim pe test
• pentru $C = 2$ se garantează că există întotdeauna soluție pentru restricțiile date

Exemplul 1

pinball.in

1 4 26
20 35 57 48

pinball.out

2

Explicație

Cerința este 1.

• $20$ are 6 divizori naturali ($1, 2, 4, 5, 10, 20$)
• $35$ are 4 divizori naturali ($1, 5, 7, 35$)
• $57$ are 4 divizori naturali ($1, 3, 19, 57$)
• $48$ are 10 divizori naturali ($1, 2, 3, 4, 6, 8, 12, 16, 24, 48$)

$\Rightarrow$ numărul de bomboane rămas $nr = 26 - 6 - 4 - 4 - 10 = 2$

Exemplul 2

pinball.in

2 4 26
20 35 57 48

pinball.out

2

Explicație

Cerința este 2.
$20$ are 6 divizori naturali, $35$ are 4 divizori naturali, $57$ are 4 divizori naturali, $48$ are 10 divizori naturali.
$\Rightarrow nr = 26 - 6 - 4 - 4 - 10 = 2$.
Un număr natural care are $2$ divizori naturali este $2$ ($\le 6\ 000\ 000\ 000$). În locul lui $2$, se putea afișa orice număr prim $P \le 6\ 000\ 000\ 000$, pentru punctaj maxim.