| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 293 | 108 | 98 | 46.226% |
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?
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.
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.
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.