Greedy Pie Eaters#10293
Farmer John has cows, conveniently labeled from to , who occasionally enjoy a change of pace from eating grass. As a special treat, Farmer John has baked pies, labeled through . Each cow enjoys pies with labels in the range [l_i, r_i] (inclusive), and no two cows enjoy the exact same range of pies. Additionally, each cow has a weight, w_i, which is an integer ranging from to 10^6.
Farmer John can select a sequence of cows, c_1, c_2, ..., c_k, who will then take turns eating in that order. However, the cows don't know how to share! When it is cow c_i's turn, she will consume all the pies she enjoys — that is, all remaining pies within the interval [l_{c_i}, r_{c_i}]. Farmer John wants to avoid the awkward situation where a cow's turn comes and there are no pies left for her to enjoy. Therefore, he needs you to compute the largest possible total weight (w_{c_1} + w_{c_2} + ... + w_{c_k}) of a sequence c_1, c_2, ..., c_k where each cow in the sequence eats at least one pie.
The first line contains two integers, n~(1 \le n \le 300) and m~(1 \le m \le m \cdot (n + 1) / 2). The next 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.
In this example, if cow eats first, then there will be nothing left for cow to eat. However, if cow eats first, cow will be satisfied by eating only the second pie.
Example 1