QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

# 4134. 保护出题人

统计

出题人铭铭认为给 SDOI 2012 出题太可怕了,因为总要被骂,于是他又给 SDOI 2013 出题了。

参加 SDOI 2012 的小朋友们释放出大量的僵尸,企图攻击铭铭的家。而你作为 SDOI 2013 的参赛者,你需要保护出题人铭铭。

僵尸从唯一一条笔直道路接近,你们需要在铭铭的房门前放置植物攻击僵尸,避免僵尸碰到房子。

第一关,一只血量为 $a_1$ 点的僵尸从距离房子 $x_1$ 米处速接近,你们放置了攻击力为 $y_1$ 点/秒的植物进行防御;第二关,在上一关基础上,僵尸队列排头增加一只血量为 $a_2$ 点的僵尸,与后一只僵尸距离 $d$ 米,从距离房 $x_2$ 米处匀速接近,你们重新放置攻击力为 $y_2$ 点/秒的植物;……;第 $n$ 关,僵尸队列共有 $n$ 只僵尸,相邻两只僵尸距离 $d$ 米,排头僵尸血量为 $a_n$ 点,排第二的僵尸血量 $a_{n-1}$,以此类推,排头僵尸从距离房子 $x_n$ 米处匀速接近,其余僵尸跟随排头同时接近,你们重新放置攻击力为 $y_n$ 点/秒的植物。

每只僵尸直线移动速度均为 $1$ 米/秒,由于植物射击速度远大于僵尸移动速度,可忽略植物子弹在空中的时间。所有僵尸同时出现并接近,因此当一只僵尸死亡后,下一只僵尸立刻开始受到植物子弹的伤害。游戏得分取决于你们放置的植物攻击力的总和 $\sum_{i=1}^n y_i$ ,和越小分数越高,为了追求分数上界,你们每关都要放置攻击力尽量小的植物。

作为 SDOI 2013 的参赛选手,你们能保护出题人么?

输入格式

第一行两个空格隔开的正整数 $n$ 和 $d$,分别表示关数和相邻僵尸间的距离。

接下来 $n$ 行每行两个空格隔开的正整数,第 $i + 1$ 行为 $A_i$ 和 $X_i$,分别表示相比上一关在僵尸队列排头增加血量为 $A_i$ 点的僵尸,排头僵尸从距离房子 $X_i$ 米处开始接近。

输出格式

一个数,$n$ 关植物攻击力的最小总和 ,保留到整数。

样例数据

样例输入

5 2
3 3
1 1
10 8
4 8
2 3

样例输出

7

子任务

测试点编号 $n = $
$1$ $100$
$2$ $500$
$3$ $1\,000$
$4$ $5\,000$
$5$ $10\,000$
$6$ $20\,000$
$7$ $50\,000$
$8$ $80\,000$
$9 \sim 10$ $10^5$

对于 $100\%$ 的数据,$1 \leq n \leq 10^5$,$1 \leq d \leq 10^{12}$,$1\leq x\leq 10^{12}$,$1 \leq a \leq 10^{12}$