Bovine Acrobatics

题目描述

农夫约翰决定让他的奶牛做一些杂技！首先，FJ 给奶牛称重，发现它们有 $N$（$1\le N\le 2\cdot 10^5$）种不同的体重。具体地，对每个 $i\in [1,N]$，有 $a_i$ 头奶牛的体重为 $w_i$（$1\le a_i\le 10^9, 1\le w_i\le 10^9$）。

他最受欢迎的特技之一是让奶牛组成平衡塔。

一座塔是一个奶牛序列，其中每头奶牛叠在下一头奶牛的上面。

如果对于每一头下方有直接位于其上的奶牛的奶牛，它的体重至少比其正上方奶牛的体重多 $K$（$1\le K\le 10^9$），则该塔是平衡的。

任意一头奶牛最多只能属于一座平衡塔。

如果 FJ 想要最多创建 $M$（$1 \le M \le 10^9$）座平衡塔，那么最多有多少头奶牛可以属于某座塔？

输入格式

第一行包含三个用空格分隔的整数 $N$、$M$ 和 $K$。 接下来的 $N$ 行每行包含两个用空格分隔的整数 $w_{i}$ 和 $a_i$。保证所有 $w_i$ 互不相同。

输出格式

如果 FJ 以最优方式帮助奶牛搭塔，输出能在平衡塔中包含的奶牛数量的最大值。

3 5 2
9 4
7 6
5 5

14

3 5 3
5 5
7 6
9 4

9

提示

FJ 可以用体重为 5、7 和 9 的奶牛创建四座平衡塔，并用体重为 5 和 7 的奶牛创建一座平衡塔。 FJ 可以用体重为 5 和 9 的奶牛创建四座平衡塔，并创建一座只有一头体重为 7 的奶牛的平衡塔。或者，他可以用体重为 5 和 9 的奶牛创建四座平衡塔，并创建一座只有一头体重为 5 的奶牛的平衡塔。 SCORING: 在第 3-5 组输入中，$M \leq 5000$ 且奶牛总数不超过 $5000$。 在第 6-11 组输入中，奶牛总数不超过 $2\cdot 10^5$。 第 12-17 组输入没有额外限制。 题目鸣谢：Eric Hsu

标签: USACO|2023|Silver

来源

USACO|2023|Silver