파일 업로드

식탐많은 친구들

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

현수에게는 MM명의 친구가 있습니다. 이 친구들은 밥을 먹는 것 외에 가끔 다른 즐거움을 느끼고 싶어합니다. 친구들을 위한 간식으로, 현수는 NN개의 탕후루(1N3001 \leq N \leq 300)를 만들었으며, 탕후루에는 1N1 \ldots N의 라벨이 붙어 있습니다. ii번째 친구는 lil_i에서 rir_i까지의 범위에 해당하는 라벨이 붙은 탕후루를 좋아합니다. 또한, 두 친구가 정확히 같은 범위의 탕후루를 좋아하는 경우는 없습니다. 각 친구에는 무게(wiw_i)가 있으며, 이는 11061 \ldots 10^6 범위의 정수입니다.

현수는 자신의 친구를 선택하여 순차적으로 탕후루를 전달하려고 합니다. 안타깝게도, 친구들은 식탐이 굉장히 많습니다. 각 친구는 자신의 차례에서, 자신이 좋아하는 탕후루를 모두 먹게됩니다. 즉, 해당 친구가 좋아하는 탕후루가 이미 다 먹혀버린 상황을 현수는 피하고 싶어합니다. 그렇기 때문에, 각각의 친구가 적어도 한 개의 탕후루를 먹을 수 있는 순서에 대해 가능한 최대 무게(wc1+wc2++wcKw_{c_1}+w_{c_2}+ \ldots+w_{c_K})를 계산하게 해주세요.

💻 입력

첫 번째 줄에는 두 개의 정수 NNMM이 주어집니다 ((1MN(N+1)2)\left(1 \le M \le \frac{N(N+1)}{2} \right).).

그 다음 MM줄에는 wiw_i, lil_i, 그리고 rir_i 세 개의 정수로 각각의 친구에 대한 정보가 주어집니다.

🖨️ 출력

유효한 순서에 대한 최대 가능 무게를 출력하세요.


💻 예제 입력 1
2 2
100 1 2
100 1 1
🖨️ 예제 출력 1
200

💡 힌트

이 예제에서, 친구 1이 먼저 탕후루를 먹는다면 친구 2가 먹을 것이 없습니다. 

그러나, 친구 2가 먼저 탕후루를 먹는다면 친구 1은 두 번째 탕후루만 먹으면 만족합니다.


출처: USACO 2019 December Contest, Platinum Problem 1. Greedy Pie Eaters