【题目大意】：
    A省有一条东西向的公路经常堵车，为解决这一问题，省政府对此展开了调查。调查后得知，这条公路两侧有很多村落，每个村落里都住着很多个信仰c教的教徒，每周日都会开着自家的车沿公路到B地去“膜拜”他们的教主，这便是堵车的原因。详细调查显示：这里总共有N个村落，并且它们都在B地的东边。编号为i的村落住有Ri个信仰c教的教徒，距离B地的距离为Ti（单位：公里）。为解决这一问题，A省政府决定在这条公路下修建一条地下快速铁路来缓解交通，并沿线修建若干个车站（B地会修建终点站，不算车站）。每名教徒都会先往B地方向开车（如果他所在村庄处恰好有车站就不必开车了），到最近的一个快速铁路车站时换乘（如果直接开到B地就不用换乘了），再通过快速铁路到B地。但A政府遇到一个难题：修建多少个车站以及在哪修建车站。一个修建车站的方案中，如果修建过多的车站则会花费过多的钱，但修建的车站少了或者修建的位置不对又会导致公路的拥堵。A政府为了协调这两方面，采用评分的方式来衡量一个方案的好坏（分数越大方案越坏）：每修建一个车站会增加m的分数，在某一次“膜拜”中（只考虑去，不考虑返回），每导致1个教徒开车行驶1公里会增加1分。现请你设计一个修建车站的方案，使得分数最小。请输出这个最小的分数。
【题目解法】：
    首先，修建车站肯定是在某个村落里
    那么我们按照T排序
    令f[i]表示前i个村落建立若干个车站且i点必须要建的最小分数
    f[i]=min(f[j]+sigma(R[k]*(T[k]-T[i])))+m (j<k<=i)
    令sumT[i]表示R[i]*T[i]的前缀和，sum[i]表示R[i]的前缀和，则：
    f[i]=min(f[j]+sumT[i]-sumT[j]-T[i]*(sum[i]-sum[j]))+m
    =min(f[j]-sumT[j]+T[i]*sum[j])+sumT[i]-T[i]*sum[i]+m
    然后把(sum[j],f[j]-sumT[j])看成平面上一个点，用一个斜率为T[i]的直线从负无穷去截他
    然后因为sum[j]单调递增
    因此用单调队列维护一个下凸壳即可
    复杂度O(N)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=40005;
struct node {long long R,T;} a[N];
int n,q[N]; long long m,f[N],sumT[N],sum[N];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline bool cmp(const node &a,const node &b)
{
    return a.T>b.T;
}
void init()
{
    n=getint(); m=getint();
    for (int i=1; i<=n; i++) a[i].T=getint(),a[i].R=getint();
    sort(a+1,a+n+1,cmp); a[n+1].T=a[n+1].R=0;
    for (int i=1; i<=n+1; i++) sumT[i]=sumT[i-1]+a[i].T*a[i].R;
    for (int i=1; i<=n+1; i++) sum[i]=sum[i-1]+a[i].R;
}
inline long long F(int i,int j)
{
    return f[j]+sumT[i]-sumT[j]-a[i].T*(sum[i]-sum[j]);
}
inline double slope(int i,int j)
{
    double x1=sum[i],y1=f[i]-sumT[i];
    double x2=sum[j],y2=f[j]-sumT[j];
    return (y2-y1)/(x2-x1);
}
void solve()
{
    int head=1,tail=1; q[1]=0;
    for (int i=1; i<=n+1; i++)
    {
        for (;(head<tail)&&(F(i,q[head])>=F(i,q[head+1]));head++);
        f[i]=F(i,q[head]); if (i!=n+1) f[i]+=m;
        for (;(head<tail)&&(slope(i,q[tail])<slope(i,q[tail-1]));tail--);
        q[++tail]=i;
    }
    printf("%lld\n",f[n+1]);
}
int main()
{
    init();
    solve();
    return 0;
}