問題一覧 > 通常問題

No.2317 Expression Menu

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 193
作問者 : 👑 amentorimaru / テスター : tatyam cleantted
お気に入りにしたユーザー ProblemId : 9211 / 自分の提出
問題文最終更新日: 2023-03-26 20:56:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 390 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。