Popularitate

popularitate

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

Se dau $K$ si $M$ grupuri de numere. Fiecare din cele $M$ grupuri contine $N{~i~}$ numere. Fie $G{~i~}$ produsul numerelor din grupul $i$. Definim popularitatea unui grup ca fiind $P$ daca $K^P^$ divide $G{~i~}$ si $K^P+1^$ nu divide $G{~i~}$, sau, echivalent, de cate ori se imparte $G{~i~}$ la $K$. Se cere sa determinati grupul cu popularitatea maxima.

Oile sunt impartite in $M$ grupuri de prieteni.

h2. Date de intrare

Fişierul de intrare $popularitate.in$ contine pe prima linie $K$, iar pe a doua linie din fisier se gaseste $M$. Pe urmatoarele $M$ linii se gasesc descrierile grupurilor. Pe linia $i+2$ prima valoare reprezinta $N{~i~}$. Ea e urmata de $N{~i~}$ numere asociate grupului $i$.

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

h2. Date de ieşire

În fişierul de ieşire $popularitate.out$ veti afisa 2 valori reprezentand popularitatea cea mai mare si grupul care are aceasta popularitate. In caz ca sunt mai multe grupuri care au popularitate maxima afisati grupul cu indice minim.

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

h2. Restricţii

* $2 ≤ K ≤ 10000000$ ({$10$} milioane)

* $1 ≤ K ≤ 100000000$

* $1 ≤ M ≤ 100$
* $1 ≤ N{~i~} ≤ 2000$

* Grupurile sunt formate din numere naturale din intervalul $[1, 100000000]$ ({$100$} milioane)
* Pentru $30%$ din teste $K$ este prim.
* Pentru $30%$ din teste $N{~i~} ≤ 100$.

* $1 ≤ VMAX ≤ 100000000$

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

| 6
3
6 2 3 5 8 12 9
4 5 7 64 11
3 4 9 81
| 4 1

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

|
h3. Explicaţie

grupul $1$ are popularitate $4$, $2 * 3 * 5 * 8 * 12 * 9 = 25920 = 6^4^ * 20$
grupul $2$ are popularitate $0$, $5 * 7 * 64 * 11 = 24640$ nu se divide cu $6$
grupul $3$ are popularitate $2$, $4 * 9 * 81 = 2916 = 6^2^ * 81$

...

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