問題一覧 > 通常問題

No.3459 Defeat Slimes

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : dyktr_06 / テスター : sepa38 くらげ おのせ tyawanmusi
ProblemId : 12951 / MMA Contest 021 (順位表) / 自分の提出
問題文最終更新日: 2026-02-27 23:42:44
MMA Contest 021の他の問題:

問題文

草原に $N$ 種類のスライムがいます。$i$ 種類目のスライムは $C_i$ 匹おり、レベルは $L_i$ で、倒すと $X_i$ だけレベルが上がります。

あなたのレベルは $Y$ であり、あなたは以下の行動を何回でも行うことができます。

  • 自身のレベル以下のスライムを $1$ 匹選び、倒す。倒されたスライムは消滅する。

$Z$ レベル以上になるためには少なくとも何匹のスライムを倒す必要があるかを答えてください。

また、$Z$ レベル以上になることが不可能な場合には -1 を出力してください。

制約

  • $1 \leq N \leq 2 \times 10^{5}$
  • $1 \leq C_i, X_i, L_i \leq 10^{18}$
  • $1 \leq Y < Z \leq 10^{18}$
  • 入力はすべて整数

入力

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

$N$ $Y$ $Z$
$C_1$ $L_1$ $X_1$
$C_2$ $L_2$ $X_2$
$\vdots$
$C_N$ $L_N$ $X_N$

出力

問題の答えを一行に出力せよ。

サンプル

サンプル1
入力
3 2 20
3 1 1
4 4 5
1 8 8
出力
5

例えば、以下のように行動することによってレベルを $20$ 以上にすることができます。

  • $1$ 種類目のスライムを $1$ 匹倒す。レベルは $3$ となる。
  • $1$ 種類目のスライムを $1$ 匹倒す。レベルは $4$ となる。
  • $2$ 種類目のスライムを $1$ 匹倒す。レベルは $9$ となる。
  • $3$ 種類目のスライムを $1$ 匹倒す。レベルは $17$ となる。
  • $2$ 種類目のスライムを $1$ 匹倒す。レベルは $22$ となる。

倒したスライムが $4$ 匹以下の場合は、レベルを $20$ 以上にすることができないため、$5$ と出力します。

サンプル2
入力
2 10 100
99 38 1
99 2357 1
出力
-1
サンプル3
入力
5 1 100000
100 1 1
100 10 10
100 100 100
100 1000 1000
100 10000 10000
出力
45

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