#PU1350. USACO 2023 December Contest, Silver — Problem 1. Bovine Acrobatics

USACO 2023 December Contest, Silver — Problem 1. Bovine Acrobatics

USACO 2023 December Contest, Silver — Problem 1. Bovine Acrobatics

题目描述

Farmer John has decided to make his cows do some acrobatics! First, FJ weighs his cows and finds that they have NN (1≤N≤2⋅1051\le N\le 2\cdot 10^5) distinct weights. In particular, for each i∈[1,N]i\in [1,N], aia_i of his cows have a weight of wiw_i (1≤ai≤109,1≤wi≤1091\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 KK (1≤K≤1091\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 MM (1≤M≤1091 \le M \le 10^9) balanced towers of cows, at most how many cows can be part of some tower?

输入格式

The first line contains three space-separated integers, NN, MM, and KK. The next NN lines contain two space-separated integers, wiw_{i} and aia_i. It is guaranteed that all wiw_i are distinct.

输出格式

(见题面原文)

数据范围

In inputs 3-5, M≤5000M \leq 5000 and the total number of cows does not exceed 50005000. In inputs 6-11, the total number of cows does not exceed 2⋅1052\cdot 10^5. Inputs 12-17 have no additional constraints. Problem credits: Eric Hsu

样例

样例 1

3 5 2
9 4
7 6
5 5
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.

样例 2

3 5 3
5 5
7 6
9 4
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.