P11297 [NOISG 2018 Prelim] Knapsack

翻译自 [NOISG 2018 Prelim B. Knapsack](https://github.com/noisg/sg_noi_archive/tree/master/2018_prelim)。

你获得了超市的“免费购物”优惠，规则如下： - 你有一个容量为 $S$ 的购物篮。超市里共有 $n$ 样东西。第 $i$ 样东西的重量 $w_i$，价值为 $v_i$，这样东西共有 $k_i$ 个。 - 你可以向你的购物篮塞入你想买的东西，前提是**这些东西的重量总和不超过购物篮的容量**。 现在，你只想知道，在满足规则的情况下，你最多能带多少价值的东西回去？ **请不要低估本题目的难度，如果你看到这就想写，请查看【数据范围】一栏**。

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

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

### 【样例 #1 解释】 拿第 $2,3,4,5$ 种东西，每种东西拿一个。 此时价值为 $15$，重量为 $8$。 ### 【样例 #2 解释】 拿完第 $1,2$ 种东西后拿两个第 $3$ 种东西。 此时价值为 $5400$，重量为 $20$。 ### 【数据范围】 | $\text{Subtask}$ | 分值 | $n\leq$ | $k\leq$ | | :----------: | :----------: | :----------: | :----------: | | $0$ | $0$ | 样例 | 样例 | | $1$ | $12$ | $1$ | - | | $2$ | $17$ | $100$ | $1$ | | $3$ | $20$ | $100$ | $10$ | | $4$ | $24$ | $100$ | $10^9$ | | $5$ | $27$ | $10^5$ | $10^9$ | | $6$（hack） | $0$ | $10^5$ | $10^9$ | 对于 $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$