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 [li, ri] (from li to ri inclusive), and no two cows enjoy the exact same range of pies. Cow i also has a weight, wi, which is an integer in the range 1...106.

Farmer John may choose a sequence of cows c1, c2,...., ck, 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 ci's turn to eat, she will consume all of the pies that she enjoys - that is, all remaining pies in the interval [lci, rci]. 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 (wc1 + wc2 + ... + wck) of a sequence c1, c2,..., ck for which each cow in the sequence eats at least one pie.

Input

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 wi, li, and ri.

Output

Print the maximum possible total weight of a valid sequence.

Example

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.