题目描述

小码哥有一个容量为$T$的魔法背包，以及$n$种魔法石，每种魔法石都有自己的体积$w_i$和魔力值$v_i$，有些魔法石十分稀有，所以只有一块，有些魔法石十分常见，所以可以认为数量是无限的。小码哥想要在装魔法石体积不超过背包容量的前提下，装的魔法石魔力值总和尽可能大。你能告诉小码哥这个最大的魔力值总和是多少吗？

输入格式

第一行输入两个整数$T,n$。 接下来$n$行，每行输入三个整数$w_i,v_i,type_i$，若$type_i=0$，表示其只有$1$个，若$type_i=1$，表示其数量是无限的。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

100 2
20 10 0
10 2 1

样例输出 #1

26

说明/提示

有$1\leq T\leq 10^4,1\leq n,w_i,v_i\leq 10^3$。