NézetNyomtat

Kemence_2011
Címkék > Feladat

Kemence

Cserép korsók kiégetésére szakosodott vállalkozó egy kemencét üzemeltet. Az égetésre érkező korsókat az érkezés sorrendjében kell a kemencében kiégetni. Egy menetben legfeljebb K korsó rakható a kemencébe. Minden korsóra adott a minimális és maximális égetési idő, percben kifejezve. Továbbá minden korsóra adott egy H határidő, ami azt jelenti, hogy a munka megkezdésétől számítva, a H időpontig el kell készülnie a kiégetésnek. Figyelembe kell venni, hogy egy menet előkészítése 1 percet vesz igénybe.

Feladat

Készíts programot, amely kiszámítja, hogy a követelmények betartásával legkevesebb mennyi idő alatt lehet kiégetni az összes korsót és meg is ad egy helyes beosztást.

Bemenet

Az első sorban a korsók N száma és a kemence K kapacitása van. (1<=N<=10000, 1<=K<=100) A következő N sor mindegyike három számot tartalmaz: a minimális és maximális égetési idő, majd a határidő. (1<=min<=max<=1000)

Kimenet

Az első sorba a szükséges égetési időt és a szükséges menetek számát kell írni. Ezután annyi sor következik, amennyi a szükséges menetek száma, és minden sorba a megfelelő menetben kiégetett első és utolsó korsó sorszáma kerül.

Példa

kemence.bekemence.ki
4 3
1 2 4
2 3 3
3 4 8
1 2 9
9 3
1 2
3 3
4 4

Tesztadatok