Farmer John’s Cow Pie Eating Sequence

Farmer John has M cows (numbered $1,\dots,M$) and baked N pies (numbered $1,\dots,N$). The $i$th cow likes to eat pies whose indices lie in the interval $[l_i,r_i]$ (inclusive). Note that no two cows share the exact same favorite interval. Each cow also has a positive integer weight $w_i$ in the range $[1,10^6]$.

Farmer John can choose a sequence of cows $c_1,c_2,\dots,c_K$, and have them eat pies in that order. When a cow eats, she consumes all the pies that are still available in her favorite interval. Unfortunately, the cows are not willing to share; so if by the time it is a cow's turn all the pies in her favorite range have already been eaten, she will be embarrassed. To avoid this awkward situation, Farmer John wants to ensure that when each cow in the sequence is about to eat, there is at least one pie remaining in her favorite interval.

Your task is to compute the maximum possible total weight, $w_{c_1}+w_{c_2}+\dots+w_{c_K}$, attainable by choosing an appropriate sequence of cows (and a valid order of eating) so that every cow in the sequence finds at least one of her favorite pies available when it is her turn.

Note: Once a cow eats, all pies in her favorite interval are removed from availability for subsequent cows.

inputFormat

The first line contains two integers M and N — the number of cows and the number of pies respectively.

Each of the next M lines contains three space‐separated integers: li, ri and wi, describing the favorite interval and the weight of the ith cow.

You may assume that $1 \le l_i \le r_i \le N$ and $1\le w_i\le 10^6$. Also, no two cows have the same pair $(l_i,r_i)$.

outputFormat

Output a single integer: the maximum total weight that can be obtained by an appropriate valid sequence of cows.

sample

2 5
1 5 10
2 3 100

110