Dan vrea sa isi construiasca o sala noua de bal si a primit oferte de la N echipe de constructori. Echipa i termina lucrarea singura in d_i luni si costa c_i unitati monetare pe luna.
Dan trebuie sa angajeze exact doua echipe, care lucreaza simultan de la inceputul pana la sfarsitul lucrarii, fiecare contribuind cu randamentul ei obisnuit (echipa i produce 1/d_i din lucrare pe luna). Daca alege echipele i si j, timpul de finalizare este 1 / (1/d_i + 1/d_j) luni, iar costul total este suma costurilor lunare ale celor doua echipe inmultita cu timpul de finalizare. Bugetul disponibil este buget unitati monetare.
Cerinta: determinati timpul minim de finalizare (ca fractie ireductibila p/q) alegand o pereche de echipe al carei cost total nu depaseste bugetul, sau afisati -1 daca nu exista nicio pereche care sa se incadreze in buget.
- Date de intrare
- Pe prima linie: N si buget. Urmeaza N linii, fiecare continand d_i si c_i (durata, respectiv costul lunar al echipei i).
- Date de iesire
- Se afiseaza timpul minim ca fractie ireductibila p/q, sau -1 daca nu exista o pereche valida.
- Restrictii
- 2 <= N <= 12 1 <= d_i, c_i <= 1000 1 <= buget <= 10000000
Exemple
Exemplul 1
Intrare
4 12 2 6 3 5 4 3 5 2
Iesire
4/3
Exemplul 2
Intrare
2 25 1 10 1 10
Iesire
1/2