A945 | Greedy Pie Eaters--Platinum

Farmer John has $M$ cows, conveniently labeled $1 \ldots M$, who enjoy the
occasional change of pace from eating grass. As a treat for the cows, Farmer
John has baked $N$ pies ($1 \leq N \leq 300$), labeled $1 \ldots N$. Cow $i$
enjoys pies with labels in the range $[l_i, r_i]$ (from $l_i$ to $r_i$
inclusive), and no two cows enjoy the exact same range of pies. Cow $i$ also
has a weight, $w_i$, which is an integer in the range $1 \ldots 10^6$.
Farmer John may choose a sequence of cows $c_1,c_2,\ldots, c_K,$ after which
the selected cows will take turns eating in that order. Unfortunately, the
cows don't know how to share! When it is cow $c_i$'s turn to eat, she will
consume all of the pies that she enjoys --- that is, all remaining pies in the
interval $[l_{c_i},r_{c_i}]$. Farmer John would like to avoid the awkward
situation occurring when it is a cows turn to eat but all of the pies she
enjoys have already been consumed. Therefore, he wants you to compute the
largest possible total weight ($w_{c_1}+w_{c_2}+\ldots+w_{c_K}$) of a sequence
$c_1,c_2,\ldots, c_K$ for which each cow in the sequence eats at least one
pie.

* Test cases 2-5 satisfy $N\le 50$ and $M\le 20$.
* Test cases 6-9 satisfy $N\le 50.$

The first line contains two integers $N$ and $M$ $\left(1\le M\le
\frac{N(N+1)}{2}\right)$.
The next $M$ lines each describe a cow in terms of the integers $w_i, l_i$,
and $r_i$.