题目描述

实验已经进行到了靠后的阶段，不过现在希蒙面临了一个选择，每个类型的实验他只能完成一个，现在知道每个实验的经费和结果，以及实验的类型（用数字1、2、3.....来表示），希蒙想知道进行能够做到的最大成果是多少

输入格式

两个数 m,n表示总重量为 m，一共有 n 件物品。

接下来 n 行，每行 3 个数 a_i,b_i,c_i，表示实验的花费，产生的成果，所属类型。

输出格式

一个数，最大产生的成果。

样例

输入样例

45 3
10 10 1
10 5 1
50 400 2

输出样例

10

数据范围与提示

$1≤m,n≤1000。$