4183 - 土壤修复

题目描述

某地检测发现共存在 N 处污染点,各污染点分布在一条直线道路上。将该道路建立数轴模型,第 i 处污染点位于坐标 P_i,其污染指数为 V_i

环境保护团队配备了一套土壤修复装置。每次使用时,需将装置部署在道路上某一坐标 x 处。装置激活后,将对以 x 为中心、半径为 D 的区间 [x-D,\ x+D] 内的所有污染点同时施加处理,使各污染点的污染指数降低 A。位于区间外的污染点不受影响。

当某个污染点的污染指数降至 0,则该污染点被修复,如果该位置再次位于修复装置处理的区间内,该位置的污染指数不会再降低。

当且仅当所有污染点的污染指数均降至 0 时,该地带视为完成修复。

请你计算:在最优部署策略下,完成全部修复所需的最少装置激活次数

输入

第一行包含三个整数 N,D,A,分别表示污染点数量、装置的覆盖半径和单次激活的处理强度。

接下来 N 行,每行包含两个整数 P_iV_i,分别表示第 i 处污染点的坐标及其初始污染指数。

输出

输出一个整数,表示完成修复所需的最少激活次数。

样例

输入

3 3 2
1 2
5 4
9 2

输出

2

输入

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5

输出

5

输入

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

输出

3000000000
说明

样例说明

样例 #1

三处污染点坐标依次为 1, 5, 9,污染指数依次为 2, 4, 2,装置覆盖半径 D=3,每次处理强度 A=2

  • 第一次:将装置部署在坐标 4,覆盖区间 [1, 7],污染点 15 均被处理,各减少 2,此时指数变为 0, 2, 2
  • 第二次:将装置部署在坐标 6,覆盖区间 [3, 9],污染点 59 均被处理,各减少 2,此时指数变为 0, 0, 0

两次激活后所有污染点清零,可以证明 1 次激活无法完成修复,故答案为 2

数据范围

测试点编号N,D,A
1N=1, D \leq 10^9, A=1
2N=1, D \leq 10^9, A=2
3 \sim 4N \leq 2 \times 10^5, D=0, A=1
5 \sim 10N \leq 2 \times 10^5, D \leq 10^9, A \leq 10^9

对于 100\% 的数据,满足 1 \leq N \leq 2\times 10^50 \leq D \leq 10^91 \leq A \leq 10^90 \leq P_i \leq 10^91 \leq V_i \leq 10^9,测试数据保证所有 P_i 互不相同。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 4 枚
难度 基础


上一题 下一题