Kemence
A feladat szövege
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:
Készíts olyan 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 KEMENCE.BE állomány 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:
A KEMENCE.KI állomány első sorába 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
| Input |
Output |
| 6 10
3 10
2 12
7 20
5 15
3 11
2 16 |
46
1 1
2 3
4 6 |
Tesztadatok
