B. 积木大厦

    传统题 1000ms 256MiB

积木大厦

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

题目描述

有 NN 种不同颜色的积木,所有积木均为正方体形状。第 ii 种颜色的积木有 CiC_i 块,每块积木的棱长均为 LiL_i 厘米。不同颜色的积木大小也是不同的。

现在要使用积木搭建大厦。一座大厦是由一块一块的积木摞起来构成的。为了让大厦保持稳定,必须满足:每一块被压在下方的积木,都比直接压在其上方的那块积木的棱长至少多 KK 厘米。当然,一座大厦也可以只由一块积木组成,它也是稳定的。

现在希望搭建不超过 MM 座稳定的大厦。

问:你最多可以使用多少块积木?

输入格式

第一行:三个整数 NN, MM, KK。

接下来 NN 行:每行两个整数 LiL_i 和 CiC_i。输入数据保证 LiL_i 两两不同。

输出格式

一个整数,表示最多使用到的积木的数量。

输入输出样例 #1

输入 #1

3 5 2
9 4
7 6
5 5

输出 #1

14

解释 #1

可以用棱长为 5,7,95,7,9 的积木搭建四座稳定的大厦,再用棱长 5,75,7 的积木搭建另一座。

输入输出样例 #2

输入 #2

3 5 3
5 5
7 6
9 4

输出 #2

9

解释 #2

可以用棱长为 5,95,9 的积木搭建四座稳定的大厦,再用棱长为 77 的一块积木搭建另一座。或者,可以用棱长为 5,95,9 的积木搭建四座稳定的大厦,再用棱长为 55 的一块积木搭建另一座。

数据范围

20% 的数据:M≤5000M ≤ 5000 且积木的总数不超过 50005000。

60% 的数据:积木的总数不超过 2×1052×10^5。

100% 的数据:1≤N≤2×1051 ≤ N ≤ 2×10^5, 1≤Ci≤109,1≤Li≤1091 ≤ C_i ≤ 10^9, 1 ≤ L_i ≤ 10^9, 1≤K≤1091 ≤ K ≤ 10^9, 1≤M≤1091 ≤ M ≤ 10^9

2026-10-22

未参加
状态
已结束
规则
IOI
题目
4
开始于
2026-10-22 7:40
结束于
2026-10-22 12:00
持续时间
4.3 小时
主持人
参赛人数
15