Farmer John 有 $M$ 头奶牛，编号为 $1 \ldots M$，它们喜欢偶尔换换口味，不再只吃草。作为给奶牛的奖励，Farmer John 烤了 $N$ 个派（$1 \leq N \leq 300$），编号为 $1 \ldots N$。第 $i$ 头奶牛喜欢编号在 $[l_i, r_i]$ 范围内的派（包含 $l_i$ 和 $r_i$），且没有两头奶牛喜欢的派的范围完全相同。第 $i$ 头奶牛还有一个权重 $w_i$，是一个 $1 \ldots 10^6$ 之间的整数。

Farmer John 可以选择一个奶牛序列 $c_1, c_2, \ldots, c_K$，选中的奶牛将按此顺序轮流进食。遗憾的是，奶牛们不懂得分享！当轮到奶牛 $c_i$ 进食时，她会吃掉所有她喜欢的派——也就是说，吃掉区间 $[l_{c_i}, r_{c_i}]$ 中所有剩余的派。Farmer John 希望避免出现这种情况：轮到某头奶牛进食时，她喜欢的派已经被吃光了。因此，他希望你计算出一个序列 $c_1, c_2, \ldots, c_K$ 的最大可能总权重（$w_{c_1} + w_{c_2} + \ldots + w_{c_K}$），使得序列中的每头奶牛都能至少吃到一个派。

子任务

• 测试点 2-5 满足 $N \le 50$ 且 $M \le 20$。
• 测试点 6-9 满足 $N \le 50$。

输入格式

第一行包含两个整数 $N$ 和 $M$ $\left(1 \le M \le \frac{N(N+1)}{2}\right)$。

接下来的 $M$ 行，每行描述一头奶牛，包含整数 $w_i, l_i$ 和 $r_i$。

输出格式

输出有效序列的最大可能总权重。

样例

输入格式 1

2 2
100 1 2
100 1 1

输出格式 1

200

说明

在这个例子中，如果第 1 头奶牛先吃，那么第 2 头奶牛将无派可吃。然而，如果第 2 头奶牛先吃，那么第 1 头奶牛可以通过只吃第二个派来满足需求。