У Фермера Джона \(M\) коров, последовательно пронумерованных \(1 \ldots M\), кушают траву.
В качестве подарка коровам ФД испёк \(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\).
ФД может выбрать последовательность коров \(c_1,c_2,\ldots, c_K,\) после чего
выбранные коровы будут кушать по очереди в указанном порядке. К несчастью, коровы
не умеют делиться. Когда настаёт очередь кушать коровы \(c_i\), она съедает все куски,
которыми она наслаждается, то есть все оставшиеся куски в интервале \([l_{c_i},r_{c_i}]\).
ФД хочет избежать неловкой ситуации, когда наступает очередь кушать коровы, но все куски,
которыми она наслаждается, уже съедены. Поэтому он хочет вычислить наибольший возможный
суммарный вес (\(w_{c_1}+w_{c_2}+\ldots+w_{c_K}\)) последовательности \(c_1,c_2,\ldots, c_K\)
для которой каждая корова съест хотя бы один кусок.
ОЦЕНИВАНИЕ:
- Тесты 2-5 удовлетворяют \(N\le 50\) and \(M\le 20\).
- тесты 6-9 удовлетворяют \(N\le 50\).
ФОРМАТ ВВОДА (файл pieaters.in):
Первая строка ввода содержит два целых числа
\(N\) и
\(M\)
\(\left(1\le M\le \frac{N(N+1)}{2}\right)\).
Каждая из последующих \(M\) строк описывает корову целыми числами
\(w_i, l_i\), \(r_i\).
ФОРМАТ ВЫВОДА (файл pieaters.out):
Выведите максимально возможный суммарный вес корректной последовательности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
100 1 2
100 1 1
|
200
|