TODO: napisati od kud je zadatak, koje natjecanje, koji razred, koja godina. (mislim da je sa Logo natjecanje nekog)

Dok je gospodin Vlatko ocjenjivao gastronomsku uslugu IKEA-e, gospodin Marko ipak je bio fokusiran isključivo na biznis. Primijetio je da, iako je već prosinac, promotivne cijene za Crni petak još uvijek vrijede pa ga je to navelo na ideju da treba invesirati u namještaj po povoljnijoj cijeni. Gospodin Marko naumio je kupiti cijeli asortiman namještaja u trgovini, ali naišao je na veliki problem. U njegov kombi ne stane sav taj namještaj. Marko nema vremena za razmišljati koji namještaj treba uzeti pa vas moli da mu pomognete.

Napišite kod koji ispisuje najmanju moguću cijenu za kupiti najviše namještaja. Markov kombi ima kapacitet :w te ga planira cijeloga popuniti. Lista :l opisuje asortiman namještaja te sadrži određeni broj dvočlanih podlisti. Svaki element može uzeti samo jedanput. Prvi element u podlisti predstavlja veličinu nekog namještaja, a drugi njegovu cijenu. Marko će popuniti cijeli kombi tako da zbroj veličina namještaja koje kupi bude jednaka :w, a cijena najmanja moguća. Uvijek će biti moguće popuniti cijeli kombi.

Ulazni podatci

Unos je u obliku: "PR NAMJESTAJ :w :l" Lista :l je u obliku: "[[2 3] [3 1]]" Varijabla :w je prirodan broj. Lista :l sadrži dvočlane podliste prirodnih brojeva. Prvi broj u svakoj podlisti predstavlja veličinu, a drugi cijenu.

Bodovanje

U testnim primjerim vrijednim ukupno 20% (32) bodova, cijena u svakoj podlisti će biti jednaka

Test primjeri:

Ulaz

PR NAMJESTAJ 10 [[2 6] [3 5] [10 17] [1 3] [7 10] [9 15] [8 12]]

Izlaz

15

Ulaz

PR NAMJESTAJ 6 [[1 2] [1 2] [2 2] [3 2] [3 2] [4 2]]

Izlaz

4