bzoj#P2153. 设计铁路
设计铁路
题目描述
A 省有一条东西向的公路经常堵车,为解决这一问题,省政府对此展开了调查。调查后得知,这条公路两侧有很多村落,每个村落里都住着很多个信仰 c 教的教徒,每周日都会开着自家的车沿公路到 B 地去「膜拜」他们的教主,这便是堵车的原因。详细调查显示:这里总共有 个村落,并且它们都在 B 地的东边。编号为 的村落住有 个信仰 c 教的教徒,距离 B 地的距离为 (单位:公里)。
为解决这一问题,A 省政府决定在这条公路下修建一条地下快速铁路来缓解交通,并沿线修建若干个车站(B 地会修建终点站,不算车站)。每名教徒都会先往 B 地方向开车(如果他所在村庄处恰好有车站就不必开车了),到最近的一个快速铁路车站时换乘(如果直接开到 B 地就不用换乘了),再通过快速铁路到 B 地。
但 A 政府遇到一个难题:修建多少个车站以及在哪修建车站。一个修建车站的方案中,如果修建过多的车站则会花费过多的钱,但修建的车站少了或者修建的位置不对又会导致公路的拥堵。A 政府为了协调这两方面,采用评分的方式来衡量一个方案的好坏(分数越大方案越坏):每修建一个车站会增加 的分数,在某一次「膜拜」中(只考虑去,不考虑返回),每导致 个教徒开车行驶 公里会增加 分。现请你设计一个修建车站的方案,使得分数最小。请输出这个最小的分数。
输入格式
输入的第一行包含两个正整数 。之后 行每行两个正整数 。
输出格式
输出一个整数,表示最小的分数。
样例输入 #1
4 20
25 3
5 3
25 2
20 5
样例输出 #1
55
样例说明 #1
样例一中,在距 B 地 处和距 B 地 处修建车站, 号村落里的教徒就不必开车了,得分 分。 号村落里的教徒直接开车到 B 地,得分 分。总共得分 分。
样例输入 #2
4 30
25 3
5 3
25 2
20 5
样例输出 #2
70
样例说明 #2
样例二中,在距 B 地 处修建车站, 号村落里的教徒就不必开车了,得分 分。 号和 号村落里的教徒先开车到距 B 地 处的车站,得分 分。 号村落里的教徒直接开车到 B 地,得分 分。总共得分 分。
数据规模与约定
对于 的数据,,,,。
提示:请注意使用 64 位整型存储某些数据和结果。