A porcelángyár égetőkemencéjéhez futószalagon érkeznek az égetésre váró tárgyak. Minden tárgynak ismert a súlya és a kiégetéséhez minimálisan szükséges idő. Az égetésre váró tárgyakat az érkezésük sorrendjében kell kiégetni. Egyszerre több tárgyat is rakhatunk a kemencébe, az összsúlyuk azonban nem haladhatja meg a kemence kapacitását. Az égetési idő egy menetben mindig a kemencébe rakott tárgyak minimális égetési idejének a maximuma kell legyen.

Írjunk programot, amely kiszámítja, hogy legkevesebb mennyi idő kell az összes tárgy kiégetéséhez, továbbá megadja azt is, hogy ezen idő eléréséhez mely tárgyakat kell egy-egy menetben a kemencében együtt égetni.

A bemenet első sora két egész számot tartalmaz; a tárgyak N (1<=N<=10000) számát és a kemence K (1<=K<=1000) kapacitását. A következő N sor mindegyike két egész számot tartalmaz; egy tárgy S (1<=S<=1000) súlyát és E (1<=E<=100) minimális égetési idejét.

Az első sorba az összes tárgy kiégetéshez minimálisan szükséges időt kell írni. A következő sorok mindegyikébe két egész számot, I-t és J-t kell írni egy szóközzel elválasztva, I az első, J pedig az utolsó tárgy sorszáma, amelyek egyszerre kerülnek a kemencébe.

Bemenet	Kimenet
6 10 3 10 2 12 7 20 5 15 3 11 2 16	46 1 1 2 3 4 6

A feladat forrása: NTOITV 2001, 3. forduló, 11-13. évfolyam

Algoritmusok: dinamikus programozás