問題一覧 > 通常問題

No.3808 Welcome to Mid Difficulty Problems

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 19
作問者 : dyktr_06 / テスター : sepa38 tyawanmusi
お気に入りにしたユーザー ProblemId : 14065 / 自分の提出
問題文最終更新日: 2026-11-20 21:13:29
yukicoder contest 524 (順位表) の他の問題:

問題文

あなたは、$N$ 問の問題が出題されるクイズ大会に出場します。

$i$ 問目のジャンルは $A_i$ であり、この問題を解くには $B_i$ 秒かかります。

あなたは好きな問題をいくつか選んで解くことができます。選んだ問題を解くのにかかる時間の合計は、$T$ 秒以下でなければなりません。

クイズ大会の得点は、解いた問題のジャンルの種類数と、解いた問題数の和です。

制限時間内に得られる得点の最大値を求めてください。

制約

  • $1 \leq N \leq 5 \times 10^5$
  • $1 \leq T \leq 10^9$
  • $1 \leq A_i \leq N$
  • $60 \leq B_i \leq 10^9$
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$N$ $T$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

出力

得られる得点の最大値を $1$ 行に出力してください。

サンプル

サンプル1
入力
5 180
1 60
1 100
2 120
2 70
3 200
出力
4

問題 $1$ と問題 $4$ を解くと、解いた問題数は $2$ であり、ジャンルの種類数は $2$ となるため、$4$ 点を得られます。

サンプル2
入力
7 9000
1 1800
2 2700
3 2700
4 2700
2 3600
1 3600
3 3600
出力
6

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