Lõikude kustutamine

시간 제한1초메모리 제한1024 MB

요약

선 위의 N개 구간과 각 구간의 삭제 비용이 주어질 때, 겹침 그래프의 모든 연결 성분이 최대 K개의 정점만 갖도록 구간을 삭제하는 최소 비용을 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 구간, 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

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.

예제3

예제 1
입력
```
5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1
```
예상 출력
```
3
```

예제 2

입력

예상 출력

예제 3

입력

6 1
1 2 1000000000
1 2 1000000000
1 2 1000000000
1 2 1000000000
1 2 1000000000
1 2 1000000000

예상 출력

5000000000