Farmer John has m cows, conveniently labeled 1...m, who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer John has baked n pies, labeled 1...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...10^6
.
Farmer John may choose a sequence of cows c[1]
, c[2]
,...., 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[ci]
, r[ci]
]. 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[c1]
+ w[c2]
+ ... + w[ck]
) of a sequence c[1]
, c[2]
,..., c[k]
for which each cow in the sequence eats at least one pie.
The first line contains two integers n (1 ≤ n ≤ 300) and m (1 ≤ m ≤ m * (n + 1) / 2). 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.
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.