問題一覧 > 通常問題

No.3459 Defeat Slimes

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 49
作問者 : dyktr_06 / テスター : sepa38 くらげ おのせ tyawanmusi
お気に入りにしたユーザー ProblemId : 12951 / 自分の提出
問題文最終更新日: 2026-02-27 23:42:44
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
MMA Contest 021 (順位表) の他の問題:

Problem Statement

There are $N$ types of slimes in a grassland. There are $C_i$ slimes of the $i$-th type; each has level $L_i$, and defeating one raises your level by $X_i$.

Your level is $Y$, and you can perform the following action any number of times.

  • Choose $1$ slime whose level is at most your own level and defeat it. The defeated slime disappears.

Find the minimum number of slimes you need to defeat in order to reach level $Z$ or higher.

If it is impossible to reach level $Z$ or higher, print -1.

Constraints

  • $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}$
  • All input values are integers.

Input

The input is given from standard input in the following format.

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

Output

Print the answer on one line.

Sample

Sample 1
Input
3 2 20
3 1 1
4 4 5
1 8 8
Output
5

For example, you can raise your level to $20$ or higher by acting as follows.

  • Defeat $1$ slime of type $1$. Your level becomes $3$.
  • Defeat $1$ slime of type $1$. Your level becomes $4$.
  • Defeat $1$ slime of type $2$. Your level becomes $9$.
  • Defeat $1$ slime of type $3$. Your level becomes $17$.
  • Defeat $1$ slime of type $2$. Your level becomes $22$.

If you defeat $4$ or fewer slimes, you cannot raise your level to $20$ or higher, so print $5$.

Sample 2
Input
2 10 100
99 38 1
99 2357 1
Output
-1
Sample 3
Input
5 1 100000
100 1 1
100 10 10
100 100 100
100 1000 1000
100 10000 10000
Output
45

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