叠罗汉

测试数据来自 system/2935

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制:1秒  内存限制:256M


【问题描述】

  小H决定让他的宠物狗表演叠罗汉!首先,小H为他的宠物狗称重,发现她们有 N1N2×105N(1≤N≤2×10^5)个不同的体重。具体来说,对于全部的 i[1,N]i∈[1,N],有 ai1ai109a_i(1≤a_i≤10^9) 只宠物狗的体重为 wi1wi109w_i(1≤w_i≤10^9) 单位。

  他最出名的节目需要宠物狗叠成平衡的罗汉塔。一座罗汉塔是一些宠物狗,每只宠物狗站在下一只宠物狗身上。一座罗汉塔是平衡的,当且仅当每一只被踩着的宠物狗,都比直接踩在它身上的那只宠物狗重至少 K1K109K(1≤K≤10^9)单位。每只宠物狗都可以成为罗汉塔的一部分。

  如果 小H 想要创造最多 M1M109M(1≤M≤10^9)座罗汉塔,最多有多少只宠物狗可以成为罗汉塔的一部分?

【输入格式】

  第一行包含三个空格分隔的整数 NMN,MKK
  接下来 NN 行,每行包含两个空格分隔的整数 wiw_iaia_i。保证所有的 wiw_i 是不同的。

【输出格式】

  输出当 小H 采用最佳方案时,罗汉塔中宠物狗的最大数目。

【输入输出样例1】

 Input

3 5 2
9 4
7 6
5 5

 Output

14

【样例1解释】

  小H 可以用体重为 5,7,9 的宠物狗创造四座平衡的罗汉塔,再用体重为 5,7 的宠物狗创造另一座。

【输入输出样例2】

 Input

3 5 3
5 5
7 6
9 4

 Output

【样例2解释】

  小H 可以用体重为 5,9 的宠物狗创造四座平衡的罗汉塔,再用体重为 7 的一只宠物狗创造另一座。或者,他可以用体重为 5,9 的宠物狗创造四座平衡的罗汉塔,再用体重为 5 的一只宠物狗创造另一座。

【测试点性质】

  测试点 353−5 满足 M5000M≤5000 且宠物狗的总数不超过 50005000
  测试点 6116−11 满足宠物狗的总数不超过 21052⋅10^5
  测试点 121712−17 没有额外限制。

【来源】

  Mr.he

定时练习(五)订正

未参加
状态
已结束
规则
OI
题目
6
开始于
2024-09-27 18:00
结束于
2024-11-08 10:00
持续时间
1000.0 小时
主持人
参赛人数
22