题目描述

有N种物品和一个容量为M的背包。第i种物品每件重量为W_i，价值为C_i，数量限制为P_i。

P_i=0表示该物品可以取无限件；P_i>0表示最多取P_i件。求在总重量不超过M的情况下，能够取得的最大总价值。

输入格式

第一行两个整数M、N。接下来N行，每行三个整数W_i、C_i、P_i。

输出格式

输出最大总价值。

样例

10 3
2 1 0
3 3 1
4 5 4

11

数据范围

1≤M≤200，1≤N≤30，1≤W_i,C_i≤10000，0≤P_i≤200。