No.2317 Expression Menu
タグ : / 解いたユーザー数 193
作問者 : 👑
amentorimaru
/ テスター :
tatyam
Problem Statement
Etowanyu, who lives in a virtual space, wants to implement some of the $N$ features that let him freely change his appearance from a menu. His initial cuteness is $10^{100}$.
Implementing the $i$-th feature raises Etowanyu's "cuteness" by $C_i$, but consumes $A_i$ menu slots and $B_i$ capacity.
The total menu slots consumed must be at most $X$, and the total capacity consumed must be at most $Y$. Also, the same feature cannot be implemented $2$ or more times.
Find the maximum amount by which Etowanyu can raise his "cuteness".
Input
$N \ X \ Y$ $A_1 \ B_1 \ C_1$ $A_2 \ B_2 \ C_2$ $\vdots$ $A_N \ B_N \ C_N$
- All inputs are integers.
- $1 \le N,X,Y,A_i,B_i \le 300$
- $1 \le C_i \le 10^9$
Output
Output the maximum amount by which the "cuteness" can be raised, followed by a newline.
Sample
Sample 1
Input
3 4 4 3 1 3 1 2 4 3 2 2
Output
7
By implementing features $i=1,2$, $4$ menu slots and $3$ capacity are consumed and the cuteness is raised by $7$. The cuteness becomes $10^{100}+7$, and the amount raised, $7$, is the answer.
With $i=2,3$, the menu slots and capacity can be used up exactly, but the cuteness is raised by $6$, which is not the maximum.
The same feature cannot be implemented twice, so $i=2$ cannot be implemented two times.
Sample 2
Input
3 5 5 100 100 100 200 200 200 300 300 300
Output
0
Etowanyu cannot implement any of the features, but he is cute just as he is.
Sample 3
Input
20 300 300 219 84 459 257 66 494 274 235 82 79 33 355 13 78 442 27 281 988 48 177 578 247 278 351 238 44 279 44 98 575 107 159 89 142 13 570 72 202 602 121 186 611 288 124 960 169 102 968 260 74 835 196 125 248 278 274 73 22 269 366
Output
1985
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。