3287. 自动送报机

单点时限: 2.0 sec

内存限制: 256 MB

有一种自动送报机可以给分布在一条直线上的 n 户人家送报。

一开始,所有的报纸都被堆积在 x=0 的位置。而这些人家呢,第 i 户人家的位置是 xi,需要 mi 份报纸。

但是,自动送报机一次只能携带最多 k 份报纸。自动送报机必须从 x=0 的位置出发,装上一些报纸,然后出发送报,然后回来装报,来来回回,直到所有人家的需求都得到满足为止。自动送报机的速度是 1,装卸报纸的时间、折返的时间可以忽略不计。

请求出送完所有报纸最少要多少时间。

输入格式

第一行有两个整数,用空格隔开,n,k (1n1 000,1k107)

接下来 n 行,每行两个整数 xi,mi (|xi|107,1mi107)

输出格式

输出一个整数:送完所有报纸需要时间的最小值。

样例

Input
4 9
-7 5
-2 3
5 8
9 5
Output
42

23 人解决,47 人已尝试。

28 份提交通过,共有 309 份提交。

6.3 EMB 奖励。

创建: 7 年,10 月前.

修改: 7 年,7 月前.

最后提交: 2 周,4 天前.

来源: 2017 ACM 「一场」测验赛

题目标签