問題一覧 > 通常問題

No.3713 海底探索

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 15
作問者 : へきぼこ　競プロのすがた / テスター : UT0911
お気に入りにしたユーザー ProblemId : 14023 / 自分の提出
問題文最終更新日: 2026-09-12 12:04:30

問題文

あなたは海底にある遺跡を調査しています。遺跡には $N$ 個の宝箱があり、持って帰ろうとすると襲い掛かってきます。
宝箱 $i$ は重さが $X_i$ 、攻撃力が $Y_i$ です。あなたは $A$ 以下の重さを持つことができ、 $B$ 以下の攻撃は耐えることができます。
重さの総和が $A$ 以下にしないといけません。また、攻撃力の総和も $B$ 以下にしないといけません。
持って帰ることができる宝箱の数の最大値を求めてください。
宝箱の攻撃力は非常に高いことがあります。

入力

$N\ A\ B$
$X_1\ Y_1$
$X_2\ Y_2$
:
$X_N\ Y_N$

制約

$1 \leq N \leq 100$
$1 \leq A \leq 100$
$1 \leq B \leq 10^9$
$1 \leq X_i \leq 100$
$1 \leq Y_i \leq 10^9$

入力は全て整数

出力

持って帰ることができる宝箱の数の最大値を求めてください。
最後に改行してください。

サンプル

サンプル1
入力
3 10 100
9 30
4 50
5 30
出力
2

$2$ 番目と $3$ 番目の宝箱を選ぶと重さの総和は $4+5=9$ 、攻撃力の総和は $50+30=80$ となり無事に持って帰られます。

サンプル2
入力
5 20 150
5 10 
4 20
8 40
2 90
7 30
出力
4

$1,2,4,5$ 番目を選べば良いです。

サンプル3
入力
3 50 100000000
10 1000000
40 1000000
20 100000000
出力
2

宝箱の攻撃力は非常に高いことがあります。

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