Lõikude kustutamine

문제

Arvteljel on antud $NN$ lõiku. Lõigud on nummerdatud $1\dots N1\; \backslash ldots\; N$. Lõigu number $ii$ otspunktid on $S_{i}S\_i$ ja $E_{i}E\_i$. Vaatleme graafi $GG$, milles igale lõigule vastab tipp ja milles kahe tipu vahel on serv, kui neile vastavatel lõikudel on ühiseid punkte (kasvõi ainult ühine otspunkt).

Nüüd on vaja saavutada, et selle graafi üheski sidususkomponendis poleks rohkem kui $KK$ tippu. Selleks võime mõned antud lõikudest kustutada. Iga lõigu $ii$ kustutamisel on kindel hind $W_{i}W\_i$. Leida lõikude kustutamiseks minimaalse koguhinnaga viis.

입력

Sisendi esimesel real on täisarvud $NN$ ja $KK$ ($1\le K\le N\le 25001\; \backslash le\; K\; \backslash le\; N\; \backslash le\; 2\backslash ,500$). Järgmisel $NN$ real on igaühel ühe lõigu kirjeldus: täisarvud $S_{i}S\_i$, $E_{i}E\_i$ ja $W_{i}W\_i$ ($1\le S_i\le E_i\le {10}^{9}1\; \backslash le\; S\_i\; \backslash le\; E\_i\; \backslash le\; 10^9$, $1\le W_i\le {10}^{9}1\; \backslash le\; W\_i\; \backslash le\; 10^9$).

출력

Väljundi ainsale reale väljastada vähim võimalik kustutatamiste koguhind.