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.
SCORING:
In this example, if cow 1 eats first, then there will be nothing left for cow 2 to eat. However, if cow 2 eats first, then cow 1 will be satisfied by eating the second pie only.
Problem credits: Benjamin Qi
