F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 2153. -- 设计铁路

2153: 设计铁路

Time Limit: 5 Sec  Memory Limit: 259 MB
Submit: 368  Solved: 201
[Submit][Status][Discuss]

Description

A省有一条东西向的公路经常堵车,为解决这一问题,省政府对此展开了调查。调查后得知,这条公路两侧有很多村落,每个村落里都住着很多个信仰c教的教徒,每周日都会开着自家的车沿公路到B地去“膜拜”他们的教主,这便是堵车的原因。详细调查显示:这里总共有N个村落,并且它们都在B地的东边。编号为i的村落住有Ri个信仰c教的教徒,距离B地的距离为Ti(单位:公里)。为解决这一问题,A省政府决定在这条公路下修建一条地下快速铁路来缓解交通,并沿线修建若干个车站(B地会修建终点站,不算车站)。每名教徒都会先往B地方向开车(如果他所在村庄处恰好有车站就不必开车了),到最近的一个快速铁路车站时换乘(如果直接开到B地就不用换乘了),再通过快速铁路到B地。但A政府遇到一个难题:修建多少个车站以及在哪修建车站。一个修建车站的方案中,如果修建过多的车站则会花费过多的钱,但修建的车站少了或者修建的位置不对又会导致公路的拥堵。A政府为了协调这两方面,采用评分的方式来衡量一个方案的好坏(分数越大方案越坏):每修建一个车站会增加m的分数,在某一次“膜拜”中(只考虑去,不考虑返回),每导致1个教徒开车行驶1公里会增加1分。现请你设计一个修建车站的方案,使得分数最小。请输出这个最小的分数。

Input

输入的第一行包含两个正整数n、m。之后n行每行两个正整数Ti、Ri。

Output

输出一个整数,表示最小的分数。

Sample Input

【样例输入1】
4 20
25 3
5 3
25 2
20 5
【样例输入2】
4 30
25 3
5 3
25 2
20 5

Sample Output

【样例输出1】
55

【样例输出2】
70
【样例说明】
样例1中,在距B地20km处和距B地25km处修建车站,1、3、4号村落里的教徒就不必开车了,得分20*2=40分。2号村落里的教徒直接开车到B地,得分3*5=15分。总共得分55分。
样例2中,在距B地20km处修建车站,4号村落里的教徒就不必开车了,得分30分。1号和3号村落里的教徒先开车到距B地20km处的车站,得分3*5+2*5=25分。2号村落里的教徒直接开车到B地,得分3*5=15分。总共得分70分。
【数据规模】
对于100%的数据,n<=40000,m<=2000000000,Ti<=1000000,Ri<=1000。
提示:请注意使用64位整型存储某些数据和结果。

HINT

Source

[Submit][Status][Discuss]

HOME Back