Perket
"Perket" je, kao što to svi znamo, naširoko poznato i svima ukusno jelo. Da bi perket bio to što jest, oni koji ga spremaju moraju veoma pažljivo birati koje sastojke iskoristiti tako da dobiju što bolju punoću okusa, a da se pritom ne odmaknu od duha tradicije.
Za pravljenje perketa na raspolaganju nam je N sastojaka. Za svakog od njih znamo njegovu kiselost K i gorcinu G. Kada koristimo više sastojaka, ukupna kiselost jela je umnožak kiselosti svakog pojedinog sastojka, a gorcina zbroj gorcina svakog iskorištenog sastojka.
Pošto perket, to svatko zna, nije ni kiseo ni gorak, sastojke je potrebno odabrati tako da apsolutna razlika kiselosti i gorcine cijelog jela bude minimalna moguća. Potrebno je iskoristiti barem jedan sastojak, jer nitko ne voli vodu za glavno jelo.
U sljedećih N redova nalaze se po dva prirodna broja odvojena razmakom, kiselost i gorčina svakog stastojka.
Ako odaberemo sve sastojke, ni kiselost ni gorčina jela neće preći 1000000000.
1
3 10Izlaz:
72
3 8
5 8Izlaz:
14
1 7
2 6
3 8
4 9Izlaz:
1Pojašnjenje trećeg primjera:
Ako odaberemo zadnja tri sastojka, tada je ukupna kiselost jednaka 2·3·4=24, a ukupna gorčina jednaka 6+8+9=23. Apsolutna razlika iznosi 1.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.