Farmer John has decided to make his cows do some acrobatics! First, FJ weighs
his cows and finds that they have \(N\) (\(1\le N\le 2\cdot 10^5\)) distinct
weights. In particular, for each \(i\in [1,N]\), \(a_i\) of his cows have a weight
of \(w_i\)
(\(1\le a_i\le 10^9, 1\le w_i\le 10^9\)).

His most popular stunt involves the cows forming balanced towers. A
tower is a sequence of cows where each cow is stacked on top of the next.
A tower is balanced if every cow with a cow directly above it has weight
at least \(K\) (\(1\le K\le 10^9\)) greater than the weight of the cow directly
above it. Any cow can be part of at most one balanced tower.

If FJ wants to create at most \(M\) (\(1 \le M \le 10^9\)) balanced towers of cows, at most
how many cows can be part of some tower?

Problem credits: Eric Hsu

SCORING

• In inputs 3-5, \(M \leq 5000\) and the total number of cows does not exceed \(5000\).
• In inputs 6-11, the total number of cows does not exceed \(2\cdot 10^5\).
• Inputs 12-17 have no additional constraints.

Problem credits: Eric Hsu

The first line contains three space-separated integers, \(N\), \(M\), and \(K\).

The next \(N\) lines contain two space-separated integers, \(w_{i}\) and \(a_i\). It
is guaranteed that all \(w_i\) are distinct.

Output the maximum number of cows in balanced towers if FJ helps the cows form towers
optimally.

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > December > Silver