Farmer John has decided to make his cows do some acrobatics! First, FJ weighs his cows and finds that they have N (1≤N≤2⋅105) distinct weights. In particular, for each i∈[1,N], ai of his cows have a weight of wi (1≤ai≤109,1≤wi≤109).
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≤K≤109) 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≤M≤109) 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, wi and ai. It is guaranteed that all wi 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 5 2
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 3
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, M≤5000 and the total number of cows does not exceed 5000.
In inputs 6-11, the total number of cows does not exceed 2⋅105.
Inputs 12-17 have no additional constraints.
Problem credits: Eric Hsu
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
