Egy házat szeretnénk felépíteni, ahol ismertek a munkafázisok (pl. üvegezés, villany bevezetése, vakolás stb.). Az építési munkákról ismert, hogy egyes feladatok elkezdése után legalább mennyi időnek kell eltelnie, amikortól bizonyos más feladatokat elkezdhetünk (pl. a villany bevezetése előtt meg kell építeni a falakat, ami $x$ nap). Egyszerre akár több munkafázison is dolgozhatunk. A ház építéséhez bérelnünk kell eszközöket az utolsónak elkezdett munkafázis első napjáig, mivel feltehetjük, hogy a legutolsó munkafázis egy nap alatt befejezhető. Tehát ha a $T$. napon kezdünk el utoljára munkafázist, akkor összesen $T\cdot P$ forint bérleti díjat kell fizetni. Az alapanyagok megvásárlása következtében minden munkafázis további költségeket jelent. A mostani feladatban úgy tekintjük, hogy az alapanyagok ára monoton csökken (azaz későbbi időpontban sosem lesz nagyobb, mint egy korábbi esetén lenne), és intervallumonként konstans. (Vagyis pl. 1‐10. napig 30 forint, 11‐20. napig 20, utána 21‐40. napig 15 forint.)
Írjunk programot, amely a feladatok egymásra épülése, a $P$ bérleti díj, illetve az egyes feladatokhoz szükséges intervallumonkénti alapanyagárak ismeretében megadja, hogy minimum mennyi pénzbe kerül a ház fölépítése, ha a lehető legügyesebben ütemezzük az egyes feladatok elkezdését.
A standard bemenet első sorában található a feladatok $N$, illetve az egymásra épülések $E$ száma, valamint a $P$ bérleti díj ($1\le N\le 30000$, $0\le E\le 100000$, $0\le P\le 1000$) szóközökkel elválasztva. A következő $E$ sor mindegyikében három szám található, példaként $\left(a_i\mathrm{,}{b}_i\mathrm{,}{c}_i\right)$, amelyek egymásra épüléseket írnak le: az $a_i$ sorszámú munka megkezdése után $c_i$ nappal lehet elkezdeni a $b_i$ sorszámú munkát ($1\le i\le E$). A következő $N$ sor az egy-egy munkához szükséges alapanyagok árainak alakulását tartalmazza a következőképpen: az első szám $K$ $\left(1\le K\le 100\right)$, és ezután $K$ darab egymáshoz illeszkedő intervallum leírása következik két-két számmal $\left(f_j\mathrm{,}{v}_j\right)$, melyek jelentése: az intervallumon $f_j$ forintba kerül megvenni az alapanyagokat az adott munkához, és a $v_j$-edik nap az intervallum utolsó napja (azaz amikor még $f_j$ forintba kerül a vásárlás) ($0\le f_j\le 1000$, $1\le v_j\le {10}^9$). Az első intervallum az 1. napon indul, a továbbiak pedig mindig az előző intervallum vége utáni napon kezdődnek ($1\le j\le K$).
A standard kimenet egyetlen sorába írjuk ki a ház fölépítésének minimális költségét.
Feltehetjük, hogy az egymásra épülésekből nem következik ellentmondás, vagyis a ház mindenképpen felépíthető. Az egyes feladatokhoz szükséges alapanyagokat a feladat elkezdésének napján kell megvennünk. Az utolsó árintervallumok minden feladatnál ugyanazon a $D$. napon végződnek ($1\le D\le {10}^9$). Az építkezést leghamarabb az 1. napon kezdhetjük, és be kell fejeznünk legkésőbb a $D$. napon.