У фермера Джона имеется m коров пронумерованных от 1 до m, которым нравится время от времени менять шаг, поедая траву. В качестве угощения для коров фермер Джон испек n пирожков пронумерованныъ от 1 до n. Корове i нравятся пироги с этикетками в диапазоне [l[i]
, r[i]
] (от l[i]
до r[i]
включительно), никакие две коровы не наслаждаются одним и тем же ассортиментом пирогов. Корова i имеет вес w[i]
, который является целым числом в диапазоне от 1 до 10^6
.
Фермер Джон может выбрать последовательность коров c[1]
, c[2]
,...., c[k]
, которые по очереди будут есть в указанном порядке. К сожалению, коровы не умеют делиться! Когда наступает очередь коровы c[i]
, она съедает все пироги, которые ей нравятся, то есть все оставшиеся пироги в интервале [l[ci]
, r[ci]
]. Фермеру Джону хотелось бы избежать неловкой ситуации, когда наступает очередь коров поесть, но все пироги, которые ей нравятся, уже съедены. Поэтому он хочет найти максимально возможный общий вес (w[c1]
+ w[c2]
+ ... + w[ck]
) последовательности c[1]
, c[2]
,..., c[k]
, в которой каждая корова съест хотя бы один пирог.
Первая строка содержит два целых числа n (1 ≤ n ≤ 300) и m (1 ≤ m ≤ m * (n + 1) / 2). Каждая из следующих m строк описывает корову в виде целых чисел w[i]
, l[i]
и r[i]
.
Выведите максимально возможный общий вес допустимой последовательности.
В этом примере если корова 1 ест первой, то корове 2 больше нечего будет есть. Однако если корова 2 будет есть первой, то корова 1 будет удовлетворена, съев только второй пирог.