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], ..., 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ța

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 ≤ P ≤ 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],...,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 va 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 ≤ n ≤ 300.000
• 1 ≤ b ≤ 100.000.000
• 1 ≤ v[i] ≤ 2.000.000, 1 ≤ i ≤ n
• pentru ambele cerințe se garantează că 1 ≤ nr ≤ 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 ≤ 6.000.000.000 pentru punctaj maxim pe test
• pentru C = 2 se garantează că există întotdeauna soluție pentru restricțiile date
• Pentru 12 puncte, C = 1, 1 ≤ n ≤ 1.000, 1 ≤ v[i] ≤ 1.000
• Pentru 38 de puncte, C = 1
• Pentru 16 puncte, C = 2, 1 ≤ n ≤ 50.000 și 1 ≤ v[i] ≤ 100.000, 1 ≤ i ≤ n. Pentru toate testele din acest subtask, există soluție P ≤ 100.000.
• Pentru 18 puncte, C = 2, 1 ≤ v[i] ≤ 1.000.000, 1 ≤ i ≤ n. Pentru toate testele din acest subtask, există soluție P ≤ 1.000.000.
• Pentru 16 puncte, C = 2

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)

Deci 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. Deci nr = 26 - 6 - 4 - 4 -10 = 2.

Un număr natural care are 2 divizori naturali este 2 ( ≤ 6.000.000.000). În locul lui 2 se putea afișa orice număr prim P ≤ 6.000.000.000, pentru punctaj maxim.