Šeštadieninė informatikos olimpiadininkų mokykla

Kadaise, Vilkijos karalystėje, mažas nepatogumas virto didele bėda.

Didžiojo ežero pakrantės visada buvo žąsų gyvenamoji vieta. Plėšrūnų nebuvo, tad žąsys buvo nesuvaldomos. Vilkijos gyventojai laikėsi atokiau nuo žąsų. Retsykiais žąsis užpuldavo kaimietį, gal nukąsdavo pirštą ar du, tačiau apskritai, žmonės laikė žąsis mažu nepatogumu.

Vieną dieną, stiprios mutacijos dėka, iš vieno kiaušinio išsirito daugiagalvis ugnimi alsuojantis drakonas. Kai drakonas užaugo, jis pradėjo grasinti sudeginsiąs karalystę. Vilkija įgavo didelę bėdą. Karalius sukvietė riterius, kad papjautų drakoną ir išgelbėtų karalystę.

Riteriai paaiškino: "Reikia nukirsti visas drakono galvas. Kiekvienas riteris gali nukirsti po vieną galvą. Drakono galvos yra skirtingų dydžių. Riteris turi tokio pat aukščio arba aukštesnis už drakono galvą, kad galėtų ją nukirsti. Riterių bendrija reikalauja, kad už galvos nukirtimą riteriui būtų sumokėta po vieną aukso monetą už kiekvieną riterio ūgio centimetrą."

Ar pakaks riterių įveikti drakoną? Kiek tai kainuos? Karalius sukvietė savo patarėjus, kad padėtų nuspręsti, kuriuos riterius samdyti. Padėkite jiems — raskite, kiek mažiausiai kainuos karalystės išgelbėjimas.

Pradiniai duomenys

Pirmoje eilutėje yra du sveikieji skaičiai: drakono galvų kiekis N ir karalystės riterių kiekis M ().

Tolesnėse N eilutėse yra po vieną sveikąjį skaičių, drakono galvos dydį, centimetrais.

Tolesnėse M eilutėse yra po vieną sveikąjį skaičių, riterio ūgį, taip pat centimetrais.

Galvų dydžiai ir riterių ūgiai neviršija 10000.

Rezultatai

Vienintelėje eilutėje pateikite mažiausią karalystės išgelbėjimo kainą. Jei karalystės išgelbėti neįmanoma, parašykite -1.

Pavyzdžiai

2 3
5
4
7
8
4

11

2 1
5
5
10

-1