题目描述

小e的背包容量为 m，现在商店里有 n 种商品。

由于在梦境中，他可以零元购，但商品的数量有限，第 i 种商品最多可以购买 s_i 件，每件商品有一个价值 w_i 和 体积 v_i。

请问小e最多可以带走多少价值的商品？

输入描述

第一行：两个整数 m,n，表示背包容量、商品种数。（1 \le m,n \le 2000）

接下来 n 行：每行三个整数 s_i,w_i,v_i，表示第 i 种商品的件数、价值、体积。（0 \le s_i,w_i,v_i \le 2000）

输出描述

一个整数，表示小e能带走的最大价值。

输入样例1

10 3
2 2 1
1 5 3 
2 10 4

输出样例1

24

HINT

样例解释：拿 2 件商品 1 和 2 件商品 3。