Kovanice

Slavko se bavi sakupljanjem antičkih kovanica. Do sada je sakupio veliku kolekciju koju sada želi izložiti na ručno izrađenoj polici kako bi se njegovi gosti mogli diviti predivnoj kolekciji. Kovanice će na polici biti poslagane tako da svaka kovanica leži na polici, susjedne se kovanice dodiruju te kovanice na rubovima dodiruju rubne stijenke police (za više detalja proučite skicu prvog primjera). Kako je izrada police jako skupa, Slavko želi poredati kovanice tako da zauzimaju što manje mjesta, odnosno da baza police bude što manja.

Ulazni podatci

U prvom su retku nalazi se prirodni broj N , broj kovanica iz teksta zadatka. U drugom retku nalazi se N prirodnih brojeva koji predstavljaju polumjere kovanica. Polumjeri kovanica su potpuni kvadrati manji od milijardu. Dodatno, omjer najveće i najmanje kovanice će biti manji od 4.

Izlazni podatci

U jedini redak ispišite traženu duljinu police kada se kovanice optimalno poslože.

Bodovanje

Podzadatak Bodovi Ograničenja

1 5 1 ≤ N ≤ 10 2 10 1 ≤ N ≤ 15 3 5 1 ≤ N ≤ 200000, postoje samo dva različita polumjera kovanica 4 30 1 ≤ N ≤ 200000

Probni primjeri

ulaz ulaz ulaz 3 5 4 16 25 36 100 100 121 144 100 100 121 144 169

izlaz izlaz izlaz

149 1120 1051

Pojašnjenje prvog probnog primjera: Lijeva slika pokazuje jedan od poredaka koji daje lošiju duljinu police (u ovom slučaju 152). Na desnoj slici je pokazan jedan od poredaka koji daju optimalnu duljinu baze police od 149.