Korondi János fazekas mester két kemencében égeti ki a termékeit. A kiégetésre váró tárgyak az elkészülés sorrendjében várakoznak a kiégetésre. Minden tárgyra rá van írva, hogy legkevesebb hány percig kell égetni a kemencében. Mindkét kemencébe egyidejűleg legfeljebb K darab tárgy rakható kiégetésre. Minden tárgyat az elkészülés sorrendjében betesz valamelyik kemencébe, mindkettőbe legalább egy tárgyat kell rakni egy menetben és a következő menet csak akkor kezdődik, ha mindkét kemence befejezte az égetést. Ha valamelyik kemencében több tárgyat éget egy menetben, akkor az égetési idő az abba a kemencébe tett tárgyak egyedi égetési idejének a maximuma. Mivel a kemencék energia fogyasztása az égetési idő függvénye, ezért a fazekasnak arra kell törekednie, hogy az összesített égetési idő a lehető legkevesebb legyen. 

Írjunk programot, ami  kiszámítja, hogy legkevesebb mennyi összesített égetési idő alatt lehet kiégetni az összes tárgyat!

A fazekas.be szöveges állomány első sora két egész számot tartalmaz, a kiégetésre váró tárgyak N számát (2 <= N <= 1000) és a két kemence egyedi K kapacitását (1 <= K <= 20), azaz egyidejűleg legfeljebb K tárgy rakható mindkét kemencébe. A második sor pontosan N egész számot tartalmaz (egy-egy szóközzel elválasztva), az i-edik szám az i-edik tárgy minimális égetési ideje. Minden égetési idő legfeljebb 20 000. 

A fazekas.ki szöveges állomány első egy egész számot tartalmazzon, a legkevesebb összesített égetési időt! A következő N sor mindegyike két egész számot tartalmazzon egy szóközzel elválasztva! Az i-edik sorban az első szám annak a menetnek a sorszáma legyen, amelyikben az i-edik tárgyat kemencébe rakjuk, a második szám pedig 1, ha az első, 2, ha a második kemencébe rakjuk égetni! A kiírást a menetek sorrendjében kell megadni! Több megoldás esetén bármelyik megadható. 

Bemenet	Kimenet
8 2 1 7 4 9 2 9 1 2	22 1 1 1 2 1 2 2 1 2 2 2 1 3 1 3 2

A feladat forrása: NTOITV 2013-2014, 2. forduló, 11-13. évfolyam

Algoritmusok: