問題一覧 > 通常問題

No.3422 Sazanka's hobby

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 85
作問者 : harel / テスター : まみめ rogi52 Guran08 syndrome hirayuu_yc 👑 qand kidodesu 👑 ArcAki Eku
お気に入りにしたユーザー ProblemId : 12868 / 自分の提出
問題文最終更新日: 2026-01-12 09:43:06
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
yukicoder contest YNUCPC Contest 2 (順位表) の他の問題:

Problem Statement

　Sazanka is growing $N$ plants. The height of the $i$-th plant on the morning of day $1$ is $a_i$, and every day it grows taller by $b_i$ during the night.
　The height of Sazanka's room is $M$. If a plant becomes taller than that, it breaks through the ceiling and the room starts to leak. To prevent this, every morning Sazanka removes up to $k$ plants from the room.
　Since Sazanka wants to look at the plants for as long as possible, he has decided to find the minimum $k$ required to keep the room from leaking.

Constraints

  • $1 \leq N \leq10^6$
  • $1 \leq M \leq10^9$
  • $0 \leq a_i \leq M$
  • $1\leq b_i \leq10^9$
  • All inputs are integers.

Input

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

$N$ $M$  
$a_1$ $b_1$  
$a_2$ $b_2$  
⋮  
$a_N$ $b_N$

Output

Output the minimum $k$ required to keep the room from leaking.

Sample

Sample 1
Input
3 5  
2 2  
2 3  
3 2
Output
2

On the night of day $1$, the heights of the plants become $4,5,5$. On the night of day $2$, they become $6,8,7$.
If $k = 1$, at most $2$ plants can be removed by the night of day $2$, so the remaining $1$ plant breaks through the ceiling.
With $k = 2$, the leak can be prevented.

Sample 2
Input
5 10  
2 4  
3 4  
1 2  
6 10  
3 4
Output
2

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