[SDOI2013]保护出题人

题目描述

出题人铭铭认为给SDOI2012出题太可怕了,因为总要被骂,于是他又给SDOI2013出题了。 参加SDOI2012的小朋友们释放出大量的僵尸,企图攻击铭铭的家。而你作为SDOI2013的参赛者,你需要保护出题人铭铭。 僵尸从唯一一条笔直道路接近,你们需要在铭铭的房门前放置植物攻击僵尸,避免僵尸碰到房子。 第一关,一只血量为$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 \limits _{i=1} ^{n} y_i$,和越小分数越高,为了追求分数上界,你们每关都要放置攻击力尽量小的植物。 作为SDOI2013的参赛选手,你们能保护出题人么?

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

7

说明

第一关:距离房子3米处有一只血量3点的僵尸,植物最小攻击力为1.00000; 第二关:距离房子1米处有一只血量1点的僵尸、3米处有血量3点的僵尸,植物最小攻击力为1.33333; 第三关:距离房子8米处有一只血量10点的僵尸、10米处有血量1点的僵尸、12米处有血量3点的僵尸,植物最小攻击力为1.25000; 第四关:距离房子8米处有一只血量4点的僵尸、10米处有血量10点的僵尸、12米处有血量1点的僵尸、14米处有血量3点的僵尸,植物最小攻击力为1.40000; 第五关:距离房子3米处有一只血量2点的僵尸、5米处有血量4点的僵尸、7米处有 血量10点的僵尸、9米处有血量1点的僵尸、11米处有血量3点的僵尸,植物最小攻击力 为2.28571。 植物攻击力的最小总和为7.26905。 对于100%的数据, 1<=n<=10^5,1<=d<=10^12,1<=x<= 10^12,1<=a<=10^12