Жадное поедание пирогов

У фермера Джона есть $m$ коров, пронумерованных от $1$ до $m$, которые время от времени любят разнообразить свой рацион травы. В качестве особого угощения фермер Джон испек $n$ пирогов, пронумерованных от $1$ до $n$. Корова $i$ любит пироги с номерами в диапазоне $[l_i,r_i]$ (включительно), и у каждой коровы диапазон любимых пирогов уникален. Кроме того, каждая корова $i$ имеет вес $w_i$, который является целым числом в диапазоне от $1$ до $10^6$.

Фермер Джон может выбрать последовательность коров $c_1,c_2,...,c_k$, которые будут по очереди есть в этом порядке. Однако коровы не умеют делиться! Когда наступает очередь коровы $c_i$, она съедает все пироги, которые ей нравятся, то есть все оставшиеся пироги в интервале $[l_{c_i},r_{c_i}]$. Фермер Джон хочет избежать неловкой ситуации, когда приходит очередь коровы, а для неё не осталось ни одного любимого пирога. Поэтому ему нужно вычислить максимальную возможную суммарную массу $(w_{c_1}+w_{c_2}+...+w_{c_k})$ последовательности $c_1,c_2,...,c_k$, где каждая корова в этой последовательности съедает хотя бы один пирог.

Входные данные

В первой строке находятся два целых числа: $n(1\le n\le 300)$ и $m(1\le m\le m\cdot (n+1)/2)$. Следующие $m$ строк описывают каждую корову тремя целыми числами: $w_i,l_i$ и $r_i$.

Выходные данные

Выведите максимально возможный общий вес допустимой последовательности.

Примеры

В этом примере, если корова $1$ будет есть первой, то для коровы $2$ не останется ничего. Однако, если корова $2$ будет есть первой, то корова $1$ будет удовлетворена, съев только второй пирог.