题目背景

翻译自 NOISG 2018 Prelim B. Knapsack。

题目描述

你获得了超市的“免费购物”优惠，规则如下：

• 你有一个容量为 $S$ 的购物篮。超市里共有 $n$ 样东西。第 $i$ 样东西的重量 $w_i$，价值为 $v_i$，这样东西共有 $k_i$ 个。
• 你可以向你的购物篮塞入你想买的东西，前提是这些东西的重量总和不超过购物篮的容量。

现在，你只想知道，在满足规则的情况下，你最多能带多少价值的东西回去？

请不要低估本题目的难度，如果你看到这就想写，请查看【数据范围】一栏。

输入格式

第一行两个正整数 $S,n$。

接下来 $n$ 行，每行三个正整数 $v_i,w_i,k_i$。

输出格式

一行一个正整数，代表你最多能带多少价值的东西回去。

15 5 
4 12 1 
2 1 1 
10 4 1 
1 1 1 
2 2 1

15

20 3 
5000 15 1 
100 1 3 
50 1 4

5400

提示

【样例 #1 解释】

拿第 $2,3,4,5$ 种东西，每种东西拿一个。

此时价值为 $15$，重量为 $8$。

【样例 #2 解释】

拿完第 $1,2$ 种东西后拿一个第 $3$ 种东西。

此时价值为 $5400$，重量为 $20$。

【数据范围】

对于 $100\%$ 的数据：

• $1 \leq w_i \leq S \leq 2000$
• $1 \leq n \leq 10^5$
• $1 \leq v_i \leq 10^6$
• $1 \leq k_i \leq 10^9$