29870번 - Lõikude kustutamine 다국어

Arvteljel on antud $N$ lõiku. Lõigud on nummerdatud $1 \ldots N$. Lõigu number $i$ otspunktid on $S_i$ ja $E_i$. Vaatleme graafi $G$, 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 $K$ tippu. Selleks võime mõned antud lõikudest kustutada. Iga lõigu $i$ kustutamisel on kindel hind $W_i$. Leida lõikude kustutamiseks minimaalse koguhinnaga viis.

Sisendi esimesel real on täisarvud $N$ ja $K$ ($1 \le K \le N \le 2\,500$). Järgmisel $N$ real on igaühel ühe lõigu kirjeldus: täisarvud $S_i$, $E_i$ ja $W_i$ ($1 \le S_i \le E_i \le 10^9$, $1 \le W_i \le 10^9$).

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