Greedy Pie Eaters

Farmer John has $m$ cows, conveniently labeled $\mathrm{1..}m$, who occasionally enjoy a change of pace from eating grass. As a special treat, Farmer John has baked $n$ pies, labeled $1$ through $n$. Each cow $i$ 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 $i$ has a weight, $w_i$, which is an integer ranging from $1$ 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.

Input

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 $m$ lines each describe a cow in terms of the integers $w_i,l_i$, and $r_i$.

Output

Print the maximum possible total weight of a valid sequence.

Examples

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, cow $1$ will be satisfied by eating only the second pie.