욕심 많은 파이 먹는 소

농부 존에게는 번호가 $1 \ldots M$으로 붙은 소가 $M$마리 있다. 소들은 풀을 뜯는 일에서 가끔 벗어나 쉬는 것을 좋아한다. 간식으로 농부 존은 번호가 $1 \ldots N$으로 붙은 파이를 $N$개 구웠다($1 \leq N \leq 300$). 소 $i$는 번호가 $l_i$부터 $r_i$까지인 파이(양 끝 포함)를 좋아한다. 두 소가 정확히 같은 범위를 좋아하는 경우는 없다. 소 $i$의 무게는 $w_i$이며, $1$ 이상 $10^6$ 이하의 정수다.

농부 존은 소의 수열 $c_1, c_2, \ldots, c_K$를 고를 수 있다. 선택된 소들은 그 순서대로 번갈아 먹는다. 소 $c_i$의 차례가 되면 그 소가 좋아하는 파이를 모두 먹는다. 즉 $[l_{c_i}, r_{c_i}]$에 남아 있는 파이를 전부 먹는다. 농부 존은 차례가 왔는데 좋아하는 파이가 이미 모두 없어진 상황을 피하고 싶다. 각 소가 파이를 적어도 한 개 먹는 수열 가운데 무게 합 $w_{c_1}+w_{c_2}+\ldots+w_{c_K}$가 가장 큰 값을 구하라.

첫 줄에 정수 $N$과 $M$이 주어진다($1\le M\le \frac{N(N+1)}{2}$). 다음 $M$개의 줄에는 소 하나마다 $w_i$, $l_i$, $r_i$가 주어진다.

유효한 수열의 무게 합의 최댓값을 출력한다.

이 예제에서 1번 소가 먼저 먹으면 2번 소가 먹을 파이가 남지 않는다. 2번 소가 먼저 먹으면 1번 소는 두 번째 파이만 먹어도 만족한다.