Bergengóciában minden évben megrendezésre kerül a Nemzeti Villamoshajtó Bajnokság, a királyság legnevesebb versenysorozata. Ennek keretében minden nagyváros egy-egy versenyt rendez, melynek helyszíne a város leghosszabb villamospályája. A versenyzők egyesével indulnak, céljuk, hogy a lehető legrövidebb idő alatt végighaladjanak a pályán.
Bár a verseny ideje alatt az utasszállítás szünetel, a teljes közúti forgalmat még egy ekkora attrakció kedvéért sem lehet leállítani. A szörnyű balesetek elkerülése érdekében ezért a versenyzők a kereszteződéseknél a piros jelzésen a verseny során sem haladhatnak át.
Írjunk programot, mely meghatározza, hogy optimális esetben mennyi idő alatt teljesíthető a teljes táv. A program a pálya leírását fájlból olvassa, az eredményt fájlba írja. A bemeneti, illetve kimeneti fájlok nevei az első, illetve második parancssori argumentumok.
A villamos eleje az $x=0$ koordinátájú pontból indul a $t=0$ időpillanatban, és minden időegység kezdetén $-1$, 0, $+1$ egységgel változtathatja (pillanatszerűen) a sebességét, mellyel ezután egységnyi ideig egyenletesen halad az $x$ tengely mentén. A villamos megállhat, de nem tolathat és nem is lépheti túl az $M$ maximális sebességet.
A kereszteződéseknél a villamos elejének kell a zöld jelzésen áthaladni, a lámpa állapotaihoz balról nyílt, jobbról zárt időintervallumok tartoznak. (Tehát az éppen pirosra váltó lámpán a villamos még áthaladhat, de az éppen zöldre váltón még nem.) Célba érkezésnek azt a pillanatot tekintjük, amikor a villamos elejének $x$ koordinátája megegyezik a pálya $L$ hosszával.
A bemenet első sorában három, szóközzel elválasztott szám szerepel: a pálya $10\le L\le 5000$ hossza, a lámpák $0\le N\le 1000$ száma, illetve a villamos $1\le M\le 30$ végsebessége. Az ezt követő $N$ db sor mindegyikében egy-egy lámpa leírása következik: a lámpa $1\le X_i\le L$ pozíciója, állapotváltásainak $1\le C_i\le 100$ száma (de összesen legfeljebb 1000 állapotváltás), majd $C_i$ db szám, az egyes piros-zöld állapotváltások $0\le T_{i\mathrm{,}j}\le 10000$ időpontja, mind szóközzel elválasztva. Kezdetben minden lámpa zöld jelzést mutat.
A kimenetben egyetlen szám szerepeljen: a teljes táv megtételéhez minimálisan szükséges idő egészrész-törtrész alakban ($ab/c$), ahol $c$ a célba érkezés sebessége.