T362036 【模板】多重背包问题

题目提供：[sunkuangzheng](https://www.luogu.com.cn/user/679936)

有 $n$ 个物品，每件物品有它的价格 $t_i$，它的价值 $a_i$ 和它数量 $p_i$ 。你有的金钱为 $m$，请找出你可以获得的最大价值。

第一行两个整数 $n,m$ ，表示物品的**类型数**（请注意 `类型数` 和 `个数` 是不同的概念）和你有的钱数。 以下 $n$ 行，每行三个正整数 $t_i,a_i,p_i$ ，分别表示它的价格、价值和数量。

一行一个整数，表示你能获得的最大价值。

| 测试点 | $1 \le n \le$ | $1 \le t_i \le$ | $1 \le a_i \le$ | $1 \le p_i \le$ |时间限制 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1 \sim 4$ | $500$ | $100$ | $10^3$ | $10$ |$\texttt{0.5s}$| | $5 \sim 19$ | $5 \times 10^3$ | $100$ | $10^3$ | $10^3$ |$\texttt{0.5s}$| | $20 \sim 25$ | $5 \times 10^4$ | $100$ | $10^3$ | $10^4$|$\texttt{2s}$|