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.

Problem credits: Benjamin Qi

SCORING

• Test cases 2-5 satisfy \(N\le 50\) and \(M\le 20\).
• Test cases 6-9 satisfy \(N\le 50.\)

Problem credits: Benjamin Qi

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\).

Print the maximum possible total weight of a valid sequence.

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > December > Platinum