rt，WA on #4

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,INF=(int)1e18+5;
int n,m,a,b,x[N],sum[N],ssum[N],dp[N][2];
deque<int>que;
double X(int id)
{
    return sum[id];
}
double Y(int id)
{
    return dp[id][0]+ssum[id];
}
double calc(int a,int b)
{
    if(X(a)==X(b))
    {
        if(Y(a)>Y(b))
            return -INF;
        return INF;
    }
    return (Y(a)-Y(b))/(X(a)-X(b));
}
bool check_front(int k)
{
    int a=que.front();
    que.pop_front();
    int b=que.front();
    que.push_front(a);
    return calc(a,b)<=k;
}
bool check_back(int node)
{
    int a=que.back();
    que.pop_back();
    int b=que.back();
    que.push_back(a);
    return calc(b,a)>=calc(a,node);
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a>>b,x[a]+=b;
    for(int i=1;i<=m;i++)
    {
        sum[i]=sum[i-1]+x[i];
        ssum[i]=ssum[i-1]+x[i]*i;
        dp[i][0]=i*sum[i-1]-ssum[i-1];
    }
    que.push_back(0);
    for(int i=1;i<=m;i++)
    {
        while(que.size()>=2&&check_front(i))
            que.pop_front();
        int j=que.front();
        dp[i][1]=dp[j][0]+i*sum[i-1]-i*sum[j]-ssum[i-1]+ssum[j];
        while(que.size()>=2&&check_back(i))
            que.pop_back();
        que.push_back(i);
    }
    for(int i=1;i<=m;i++)
        dp[i][0]=dp[i][1];
    que.clear();
    que.push_back(0);
    for(int i=1;i<=m;i++)
    {
        while(que.size()>=2&&check_front(i))
            que.pop_front();
        int j=que.front();
        dp[i][1]=dp[j][0]+i*sum[i-1]-i*sum[j]-ssum[i-1]+ssum[j];
        while(que.size()>=2&&check_back(i))
            que.pop_back();
        que.push_back(i);
    }
    for(int i=1;i<=m;i++)
        dp[i][0]=dp[i][1];
    que.clear();
    que.push_back(0);
    for(int i=1;i<=m;i++)
    {
        while(que.size()>=2&&check_front(i))
            que.pop_front();
        int j=que.front();
        dp[i][1]=dp[j][0]+i*sum[i-1]-i*sum[j]-ssum[i-1]+ssum[j];
        while(que.size()>=2&&check_back(i))
            que.pop_back();
        que.push_back(i);
    }
    cout<<dp[m][1];
    return 0;
}