У фермера Джона имеется m коров пронумерованных от 1 до m, которым нравится время от времени менять шаг, поедая траву. В качестве угощения для коров фермер Джон испек n пирожков пронумерованныъ от 1 до n. Корове i нравятся пироги с этикетками в диапазоне [li, ri] (от li до ri включительно), никакие две коровы не наслаждаются одним и тем же ассортиментом пирогов. Корова i имеет вес wi, который является целым числом в диапазоне от 1 до 106.

Фермер Джон может выбрать последовательность коров c1, c2,...., ck, которые по очереди будут есть в указанном порядке. К сожалению, коровы не умеют делиться! Когда наступает очередь коровы ci, она съедает все пироги, которые ей нравятся, то есть все оставшиеся пироги в интервале [lci, rci]. Фермеру Джону хотелось бы избежать неловкой ситуации, когда наступает очередь коров поесть, но все пироги, которые ей нравятся, уже съедены. Поэтому он хочет найти максимально возможный общий вес (wc1 + wc2 + ... + wck) последовательности c1, c2,..., ck, в которой каждая корова съест хотя бы один пирог.

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

Первая строка содержит два целых числа n (1 ≤ n ≤ 300) и m (1 ≤ m ≤ m * (n + 1) / 2). Каждая из следующих m строк описывает корову в виде целых чисел wi, li и ri.

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

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

Пример

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