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

У фермера Джона є $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$ буде задоволена, з'ївши лише другий пиріг.