Programozás‎ > ‎Feladatok‎ > ‎

Kemence

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.

Feladat

Í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.

Bemenet

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.

Kimenet

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.

Példa

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


Tesztadatok

Címkék

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