{"problem":{"name":"[USACO23DEC] Bovine Acrobatics S","description":{"content":"Farmer John 决定让他的奶牛表演杂技！首先，FJ 为他的奶牛称重，发现她们有 $N$（$1\\le N\\le 2\\times 10^5$）个不同的体重。具体来说，对于全部的 $i\\in [1,N]$，有 $a_i$ 只奶牛的体重为 $w_i$ 单位（$1\\le a_i\\le 10^9, 1\\le w_i\\le 10^9$）。 他最出名的节目需要奶牛叠成**平衡的奶牛塔**。一座**奶牛塔","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9977"},"statements":[{"statement_type":"Markdown","content":"Farmer John 决定让他的奶牛表演杂技！首先，FJ 为他的奶牛称重，发现她们有 $N$（$1\\le N\\le 2\\times 10^5$）个不同的体重。具体来说，对于全部的 $i\\in [1,N]$，有 $a_i$ 只奶牛的体重为 $w_i$ 单位（$1\\le a_i\\le 10^9, 1\\le w_i\\le 10^9$）。\n\n他最出名的节目需要奶牛叠成**平衡的奶牛塔**。一座**奶牛塔**是一些奶牛，每只奶牛站在下一只奶牛身上。一座奶牛塔是**平衡的**，当且仅当每一只被踩着的奶牛，都比**直接**踩在它身上的那只奶牛重至少 $K$（$1\\le K\\le 10^9$）单位。每只奶牛都可以成为奶牛塔的一部分。\n\n如果 FJ 想要创造最多 $M$（$1 \\le M \\le 10^9$）座奶牛塔，最多有多少只奶牛可以成为奶牛塔的一部分？\n\n## Input\n\n第一行包含三个空格分隔的整数 $N$，$M$ 和 $K$。\n\n接下来 $N$ 行，每行包含两个空格分隔的整数 $w_i$ 和 $a_i$。保证所有的 $w_i$ 是不同的。\n\n## Output\n\n输出当 FJ 采用最佳方案时，奶牛塔中奶牛的最大数目。\n\n[samples]\n\n## Note\n\n### 样例解释 1\n\nFJ 可以用体重为 $5,7,9$ 的奶牛创造四座平衡的奶牛塔，再用体重为 $5,7$ 的奶牛创造另一座。\n\n### 样例解释 2\n\nFJ 可以用体重为 $5,9$ 的奶牛创造四座平衡的奶牛塔，再用体重为 $7$ 的一只奶牛创造另一座。或者，他可以用体重为 $5,9$ 的奶牛创造四座平衡的奶牛塔，再用体重为 $5$ 的一只奶牛创造另一座。\n\n### 测试点性质\n\n- 测试点 $3-5$ 满足 $M \\le 5000$ 且奶牛的总数不超过 $5000$。\n- 测试点 $6-11$ 满足奶牛的总数不超过 $2\\cdot 10^5$。\n- 测试点 $12-17$ 没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9977","tags":["贪心","USACO","堆","2023","O2优化","排序"],"sample_group":[["3 5 2\n9 4\n7 6\n5 5","14"],["3 5 3\n5 5\n7 6\n9 4","9"]],"created_at":"2026-03-03 11:09:25"}}