题目描述

在《Harry Potter and the Chamber of Secrets》中，Ron的魔杖因为坐他老爸的Flying Car撞到了打人柳，不幸被打断了，

从此之后，他的魔杖的魔力就大大减少，甚至没办法执行他施的魔咒，这为Ron带来了不少的烦恼。

这天上魔药课，Snape要他们每人配置一种魔药（不一定是一样的），Ron因为魔杖的问题，不能完成这个任务，他请Harry在魔药课上(自然是躲过了Snape的检查)帮他配置。

现在Harry面前有两个坩埚，有许多种药材要放进坩埚里，但坩埚的能力有限，无法同时配置所有的药材。

一个坩埚相同时间内只能加工一种药材，但是不一定每一种药材都要加进坩埚里。

加工每种药材都有必须在一个起始时间和结束时间内完成（起始时间所在的那一刻和结束时间所在的那一刻也算在完成时间内），每种药材都有一个加工后的药效。

现在要求的就是Harry可以得到最大的药效。

输入格式

输入文件的第一行有2个整数，一节魔药课的t（1≤t<≤500）和药材数n（1≤n≤100）。

输入文件第2行到n+1行中每行有3个数字，分别为加工第i种药材的起始时间t1、结束时间t2、（1≤t1≤t2≤t）和药效w（1≤w≤100）。

输出格式

只有一行，只输出一个正整数，即为最大药效。

样例数据

input

7 4
1 2 10
4 7 20
1 3 2
3 7 3

output

35

【注释】 　　本题的样例是这样实现的：第一个坩埚放第1、4种药材，第二个坩埚放第2、3种药材。这样最大的药效就为10+20+2+3=35。

数据规模与约定

对于30%的数据 1<=t<=500 1<=n<=15 1<=w<=100 1<=t1<=t2<=t

对于100%的数据 1<=t<=500 1<=n<=100 1<=w<=100 1<=t1<=t2<=t

时间限制：$ 1 \text {s}$

空间限制：$ 256 \text {MB}$