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.

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. 

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) 

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. 

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

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

Algoritmusok:

megoldás