Farmer John 有 \(M\) 头奶牛，为了方便，编号为 $1\ldots M$。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。
Farmer John 一天烤了 \(N\) 个派请奶牛吃，这 \(N\) 个派编号为 $1\ldots N$。第 \(i\) 头奶牛喜欢吃编号在 \([l_i,r_i]\) 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 \(i\) 头奶牛有一个体重 \(w_i\)，这是一个在 \([1, 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}\)）是多少。

Farmer John has \(M\) cows, conveniently labeled $1 \ldots M$, who enjoy the occasional change of pace from eating grass.
As a treat for the cows, Farmer John has baked \(N\) pies ($1 \leq N \leq 300$), labeled $1 \ldots 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 \ldots 10^6$.

Farmer John may choose a sequence of cows \(c_1,c_2,\ldots, 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_{c_i},r_{c_i}]\).
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_{c_1}+w_{c_2}+\ldots+w_{c_K}\)) of a sequence \(c_1,c_2,\ldots, c_K\) for which each cow in the sequence eats at least one pie.

对于全部数据，$1\le N\le 300,1\le M\le \frac{N(N-1)}{2},1\le l_i\le r_i\le N,1\le w_i\le 10^6$。

对于测试点 $2\sim 5$，满足 \(N\le 50,M\le 20\)；

对于测试点 $6\sim 9$，满足 \(N\le 50\)。

样例说明

在这个样例中，如果奶牛 $1$ 先吃，那么奶牛 $2$ 就吃不到派了。然而，先让奶牛 $2$ 吃，然后奶牛 $1$ 只吃编号为 $2$ 的派，仍可以满足条件。