题目描述

有 $n$ 种物品和一个容量为 $V$ 的背包。第 $i$ 种物品的体积是 $c_i$ ，得到的价值是 $v_i$， 有 $s_i$ 件。求解将哪些物品装入背包可使价值总和最大。

输入格式

第一行是两个整数 $V$ 和 $n$（$1 \le n \le 100, 1 \le V \le 10^5$）。

接下来 $n$ 行，每行三个数 $c_i, v_i, s_i$，分别代表第 $i$ 种物品的体积、价值和数量（$1 \le c_i, s_i \le 10^5, 1 \le w_i \le 1000$）。

输出格式

输出能得到的最大价值。

样例

15 4
4 10 5
3 7 4
12 12 2
9 8 7

37