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.be | kemence.ki |
4 3 1 2 4 2 3 3 3 4 8 1 2 9 |
9 3 1 2 3 3 4 4 |