Жадне поїдання пирогів#10293

Жадне поїдання пирогів

1 секунда

128 мегабайтів

Легка

У фермера Джона є $m$ корів, пронумерованих від $1$ до $m$ , які час від часу люблять урізноманітнювати свій раціон трави. Як особливе частування фермер Джон спік $n$ пирогів, пронумерованих від $1$ до $n$ . Корова $i$ любить пироги з номерами в діапазоні $[l_{i}, r_{i}]$ [l_i, r_i] (включно), і у кожної корови діапазон улюблених пирогів унікальний. Крім того, кожна корова $i$ має вагу $w_{i}$ w_i, яка є цілим числом у діапазоні від $1$ до $1 0^{6}$ 10^6.

Фермер Джон може обрати послідовність корів $c_{1}, c_{2}, ..., c_{k}$ c_1, c_2, ..., c_k, які будуть по черзі їсти в цьому порядку. Однак корови не вміють ділитися! Коли настає черга корови $c_{i}$ c_i, вона з'їдає всі пироги, які їй подобаються, тобто всі залишені пироги в інтервалі $[l_{c_{i}}, r_{c_{i}}]$ [l_{c_i}, r_{c_i}]. Фермер Джон хоче уникнути незручної ситуації, коли приходить черга корови, а для неї не залишилося жодного улюбленого пирога. Тому йому потрібно обчислити максимальну можливу сумарну масу $(w_{c_{1}} + w_{c_{2}} + ... + w_{c_{k}})$ (w_{c_1} + w_{c_2} + ... + w_{c_k}) послідовності $c_{1}, c_{2}, ..., c_{k}$ c_1, c_2, ..., c_k, де кожна корова в цій послідовності з'їдає хоча б один пиріг.

Вхідні дані

У першому рядку знаходяться два цілі числа: $n (1 \leq n \leq 300)$ n~(1 \le n \le 300) і $m (1 \leq m \leq m \cdot (n + 1) /2)$ m~(1 \le m \le m \cdot (n + 1) / 2). Наступні $m$ рядків описують кожну корову трьома цілими числами: $w_{i}, l_{i}$ w_i, l_i і $r_{i}$ r_i.

Вихідні дані

Виведіть максимально можливу загальну вагу допустимої послідовності.

Приклади

У цьому прикладі, якщо корова $1$ буде їсти першою, то для корови $2$ нічого не залишиться. Однак, якщо корова $2$ буде їсти першою, то корова $1$ буде задоволена, з'ївши лише другий пиріг.

Приклад 1