問題一覧 > 通常問題

No.2317 Expression Menu

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 180
作問者 : 👑 amentorimaruamentorimaru / テスター : tatyamtatyam cleanttedcleantted
2 ProblemId : 9211 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-26 20:56:41

問題文

仮想空間に住んでいるエトワーニュくんはメニューから自分の姿を自由に変えることのできる $N$ 個の機能からいくつかを実装したいと考えています。最初のかわいさは $10^{100}$ です。


$i$ 番目の機能が実装できるとエトワーニュくんは $C_i$ の「かわいさ」が上がりますが、メニュー枠を $A_i$ 、容量を $B_i$ 消費します。

消費するメニュー枠は合計で $X$ 以下、容量は合計で $Y$ 以下である必要があります。また、同じ機能を $2$ つ以上実装することはできません。

エトワーニュくんの上げられる「かわいさ」の最大値を求めてください。

入力

$N \ X \ Y$
$A_1 \ B_1 \ C_1$
$A_2 \ B_2 \ C_2$
$\vdots$
$A_N \ B_N \ C_N$
  • 入力は全て整数
  • $1 \le N,X,Y,A_i,B_i \le 300$
  • $1 \le C_i \le 10^9$

出力

上げられる「かわいさ」の最大値を出力し、最後に改行してください。

サンプル

サンプル1
入力
3 4 4
3 1 3
1 2 4
3 2 2
出力
7

$i=1,2$ の機能を実装することでメニュー枠 $4$ ,容量 $3$ を消費しかわいさを $7$ 上げることができ、かわいさは $10^{100}+7$ になり、上がった「かわいさ」の $7$ が答えです。

$i=2,3$ でもメニュー枠と容量をぴったり使い切ることができますが、上がるかわいさは $6$ で最大ではありません。

同じ機能を二つ実装することはできないので $i=2$ を二回実装することはできません。

サンプル2
入力
3 5 5
100 100 100
200 200 200
300 300 300
出力
0

エトワーニュくんはどの機能も実装することができませんがそのままでもかわいいです。

サンプル3
入力
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
出力
1985

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。