题目描述

小码哥有一个容量为$T$的背包，有$n$种物品，第$i$种物品的价值为$v_i$，体积为$w_i$，有$k_i$个该种物品。小码哥要往背包里装一些物品，这些物品的体积之和不能大于背包的容量。小码哥希望这些物品的价值之和最大，你能告诉他最大的价值是多少吗？

输入格式

第一行输入两个整数$T,n$。 接下来$n$行，每行输入三个整数$w_i,v_i,k_i$。

输出格式

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

样例输入 #1

100 3
50 50 3
49 30 5
1 30 1

样例输出 #1

110

说明/提示

有$1\leq T\leq 10^4,\sum k,n,w_i,v_i\leq 1000$。