1355: [STT2024MarR1] 莳花弄草 Ⅴ
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：38
解决：17
题目描述
### 题目背景
在种完花后，三花猫 XXY、猪猪五花肉、地地晚上不睡觉，蹲在窗户守着花园，以求看清不速之客的真面目。
三只通过蹲守，发现花园破坏者是一只巨大的蝴蝶，浑身流光溢彩。三花猫 XXY 和猪猪五花肉直接被吓晕了，地地直接吓睡着了。第二天，三只在村里打听，竟然是传说中的邪恶蝴蝶。这引起了桃花源的恐慌。
三只打算再次重建花园，然而，由于前几次花园重建，三只已经一贫如洗。
### 题目描述
花园的面积是 $M$，现在地里被破坏得什么也没有。三只目前仅剩 $K$ 元。集市上有 $N$ 种花，第 $i$ 种花的占地面积为 $w_i$，价格为 $v_i$，美观度为 $p_i$，由于现在是秋初，百花凋零，所以市面上每种花都只能买一簇。
三只希望能找到一种方法，让花园内花在不超过占地面积、花费不超过余额的情况下，美观度之和最大。
输入
第一行两个整数 $N,M,K$，表示花的种数和花园面积，三只剩余的钱数。
接下来 $N$ 行，每行有两个整数 $w_i$，$v_i$，$p_i$，表示这种花的占地面积、价格、美观度。
接下来 $N$ 行，每行有两个整数 $w_i$，$v_i$，$p_i$，表示这种花的占地面积、价格、美观度。
输出
一个数，表示最大的花园美观度和。
样例输入 复制
3 10 5
4 1 2
3 4 9
3 2 2样例输出 复制
11提示
**【样例 #1 解释】**
购买 $1,2$ 号花，可以获得最大的美观度。
**【数据范围】**
对于 $50\%$ 的数据，$1 \leq N,M,K \leq 10$。
对于 $100\%$ 的数据，$1 \leq N,M,K \leq 5 \times 10^2$，$0 \leq v_i,w_i \leq M$，$1 \leq p_i \leq 10^4$。