USACO $2023$ December Contest, Silver

Return to Problem List

Problem $1.$ Bovine ACrobatics

Time Remaining: $3hrs,59$min,$46sec$

Not submitted yet

English $($en$)vv$

Farmer John has decided to make his cows do some acrobatics! First, FJ weighs his cows and finds that they have $N(1N2*{10}^5)$ distinct weights. In particular, for each iin$[1,N],a_i$ of his cows have a weight of $)a_i{10}^9,1w_i({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({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({10}^9$ balanced towers of cows, at most how many cows can be part of some tower?

INPUT FORMAT $($pipe stdin$)$:

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 FORMAT $($pipe stdout$)$:

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

SAMPLE INPUT:

$3,52$

$9,4$

$7,6$

$5,5$

SAMPLE OUTPUT:

$14$

FJ can create four balanced towers with cows of weights $5,7,$ and $9,$ and one balanced tower with cows of weights $5$ and $7.$

SAMPLE INPUT:

$3,5$

$5,5$

$7,6$

$9,4$

SAMPLE OUTPUT:

$9$

FJ can create four balanced towers with cows of weights $5$ and $9,$ and one balanced tower with a cow of weight $7.$ Alternatively, he can create four balanced towers with cows of weights $5$ and $9,$ and one balanced tower with a cow of weight $5.$

SCORING:

In inputs $3-5,M5000$ and the total number of cows does not exceed $5000.$

In inputs $6-11,$ the total number of cows does not exceed $2*{10}^5.$

Inputs $12-17$ have no additional constraints.

Problem credits: Eric Hsu