1354: [STT2024MarR1] 莳花弄草 Ⅳ
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：110
解决：35
题目描述
### 题目背景
地地种完花后，三花猫 XXY 和猪猪五花肉受到激励，振作起来了。
于是他们在花园里开心地玩耍。
然而，没过几天，在某天早晨，三只又发现花园里所有的花被破坏了。
三花猫 XXY 和猪猪五花肉直接被吓晕了。地地非常愤怒，打算要把毁花贼绳之以法。
### 题目描述
在捉贼之前，需要先重建花园。花园的面积是 $M$，现在花园里被破坏得什么也没有。集市上有 $N$ 种花，第 $i$ 种花的占地面积为 $w_i$，美观度为 $p_i$，由于现在是夏末，鲜花逐渐变少，所以市面上有些花能购无限入，有些花只能购有限入。
三只希望能找到一种方法，让花园内花在不超过占地面积的情况下，美观度之和最大。
输入
第一行两个整数 $N,M$，表示花的种数和花园面积。
接下来 $N$ 行，每行有两个整数 $w_i$，$p_i$，$k_i$，表示这种花的占地面积、美观度以及这种花的库存，如果 $k_i=0$ 则意味着可以无限购入。
接下来 $N$ 行，每行有两个整数 $w_i$，$p_i$，$k_i$，表示这种花的占地面积、美观度以及这种花的库存，如果 $k_i=0$ 则意味着可以无限购入。
输出
一个数，表示最大的花园美观度和。
样例输入 复制
3 10
3 4 2
1 1 0
9 11 1样例输出 复制
12提示
**【样例 #1 解释】**
购买 $1$ 号花两簇，$2$ 号花四簇，可以获得最大的美观度。
购买 $2$ 号花一簇，$3$ 号花一簇，也可以获得最大的美观度。
**【数据范围】**
对于 $30\%$ 的数据，$1 \leq N,M,k_i \leq 10^2$。
对于 $60\%$ 的数据，$1 \leq N,M,k_i \leq 10^3$。
对于 $100\%$ 的数据，$1 \leq N \leq 10^3$，$1 \leq M,k_i \leq 2 \times 10^4$，$1 \leq w_i \leq M$，$1 \leq p_i \leq 10^4$。