#CW27. 层塔陈列(towers)

层塔陈列(towers)

题目描述

小 W 要用仓库中的展品搭建至多 mm 座陈列塔。仓库里有 nn 种重量不同的展品,第 ii 种展品的重量为 xix_i,共有 cic_i 个;所有 xix_i 两两不同。

一座塔由若干展品从下到上叠放,可以只含一个展品。为了保持稳定,塔中任意两个相邻展品都要满足“下方展品的重量 −- 上方展品的重量 ≥d\ge d”。

每个展品最多使用一次,也可以不使用。不同塔之间没有额外限制。

请计算这些塔最多能使用多少个展品。

输入格式

第一行输入三个整数 n,m,dn,m,d。

接下来 nn 行,第 ii 行输入两个整数 xi,cix_i,c_i,表示一种展品的重量和数量。

输出格式

输出一个整数,表示最多可以使用的展品数量。

样例 1 输入

4 2 4
1 2
4 1
6 2
10 1

样例 1 输出

5

样例 1 解释

可以搭建重量序列分别为 10,6,110,6,1 和 6,16,1 的两座塔,共使用 55 个展品。每个序列都按从下到上的顺序书写。

样例 2 输入

5 3 3
2 4
3 2
5 1
8 5
12 2

样例 2 输出

9

数据范围

对于所有测试数据,保证:

  • 1≤n≤2×1051 \le n \le 2\times 10^5;
  • 1≤m,d,xi,ci≤1091 \le m,d,x_i,c_i \le 10^9;
  • 所有 xix_i 两两不同。
数据类别 分值 测试点 附加条件
A 10 1∼21\sim 2 n≤20n \le 20 且 ci≤20c_i \le 20
B 15 3∼53\sim 5 n≤1000n \le 1000 且 ∑ci≤5000\sum c_i \le 5000
C 20 6∼96\sim 9 ∑ci≤2×105\sum c_i \le 2\times 10^5
D 25 10∼1410\sim 14 m≤5000m \le 5000
E 30 15∼2015\sim 20 无额外限制