aliens

Aliens

bq. Extraterestrii sunt printre noi.

Gica fost rapit de extraterestri. Pe nava mama, el afla cate ceva despre noua civilizatie. Astfel descopera ca matematica pe care o cunosc acesti extraterestri este oarecum limitata. Studiind manualele acestora constata ca ei au descoperit doar numerele care se scriu ca produs de {$2$}, {$3$} sau {$5$}. De exemplu, extraterestrii cunosc numerele {$45$} sau {$60$}, dar nu cunosc numerele {$1$}, {$11$} sau {$42$}.

Gica fost rapit de extraterestri. Pe nava mama, el afla cate ceva despre noua civilizatie. Astfel descopera ca matematica pe care o cunosc acesti extraterestri este oarecum limitata. Studiind manualele acestora constata ca ei au descoperit doar numerele care se scriu ca produs de {$2$}, {$3$} sau {$5$}. In plus, extraterestrii cunosc numarul {$1$}. De exemplu, extraterestrii cunosc numerele {$45$} sau {$60$}, dar nu cunosc numerele {$11$} sau {$42$}.

Intr-o zi, dupa o lunga convietuire armonioasa, extraterestrii se hotarasc sa il elibereze pe Gica, daca si numai daca acesta da dovada de o inteligenta deosebita. In acest scop, i se ofera $N$ fractii de forma {$x{~i~} / y{~i~}$} (evident, toate numerele {$x{~i~}$} si {$y{~i~}$} sunt numere cunoscute de catre extraterestri) si i se cere sa aleaga anumite fractii din cele $N$ astfel incat produsul fractiilor sa fie maxim posibil, si, in plus, acest produs sa fie numar natural.
Primind $N$ fractii cu numaratorul si numitorul numere cunoscute de extraterestri, sa se determine fractiile care trebuiesc selectate astfel incat produsul lor sa fie numar natural si sa fie maxim posibil.

h2. Restrictii

* $1 ≤ N ≤ 500$
* Fiecare numar din cele date nu depaseste $2$ miliarde

* $1 ≤ N ≤ 50$
* Fiecare numar din cele date nu depaseste $400 000 000$

* Fiecare fractie poate fi selectata cel mult o data

* Se garanteaza ca oricum am selecta fractii din cele date, produsul fractiilor selectate este un numar rational din intervalul {$[10^(-100)^, 10^100^]$}.

* Se garanteaza ca exista cel putin o solutie

h2. Exemplu

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

2404