[USACO23DEC] Bovine Acrobatics S

Luogu
IDLGP9977
Time1000ms
Memory256MB
DifficultyP4
贪心USACO2023O2优化排序
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$)。 他最出名的节目需要奶牛叠成**平衡的奶牛塔**。一座**奶牛塔**是一些奶牛,每只奶牛站在下一只奶牛身上。一座奶牛塔是**平衡的**,当且仅当每一只被踩着的奶牛,都比**直接**踩在它身上的那只奶牛重至少 $K$($1\le K\le 10^9$)单位。每只奶牛都可以成为奶牛塔的一部分。 如果 FJ 想要创造最多 $M$($1 \le M \le 10^9$)座奶牛塔,最多有多少只奶牛可以成为奶牛塔的一部分? ## Input 第一行包含三个空格分隔的整数 $N$,$M$ 和 $K$。 接下来 $N$ 行,每行包含两个空格分隔的整数 $w_i$ 和 $a_i$。保证所有的 $w_i$ 是不同的。 ## Output 输出当 FJ 采用最佳方案时,奶牛塔中奶牛的最大数目。 [samples] ## Note ### 样例解释 1 FJ 可以用体重为 $5,7,9$ 的奶牛创造四座平衡的奶牛塔,再用体重为 $5,7$ 的奶牛创造另一座。 ### 样例解释 2 FJ 可以用体重为 $5,9$ 的奶牛创造四座平衡的奶牛塔,再用体重为 $7$ 的一只奶牛创造另一座。或者,他可以用体重为 $5,9$ 的奶牛创造四座平衡的奶牛塔,再用体重为 $5$ 的一只奶牛创造另一座。 ### 测试点性质 - 测试点 $3-5$ 满足 $M \le 5000$ 且奶牛的总数不超过 $5000$。 - 测试点 $6-11$ 满足奶牛的总数不超过 $2\cdot 10^5$。 - 测试点 $12-17$ 没有额外限制。
Samples
Input #1
3 5 2
9 4
7 6
5 5
Output #1
14
Input #2
3 5 3
5 5
7 6
9 4
Output #2
9
API Response (JSON)
{
  "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他最出名的节目需要奶牛叠成**平衡的奶牛塔**。一座**奶牛塔...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments