【题目描述】：

【题目解法】：
    设答案为x
    显然对于每个i，满足a1/x+...+ai/x<=x1+(i-1)*d
    x>=(a1+...+ai)/(x1+(i-1)*d)
    我们把(x1+(i-1)*d,a1+...+ai)看成二维平面上的一个点
    显然后面那个式子去最大时在凸包上
    考虑每次攻击只是在最前面增加了一个点，而其他的点只是整体平移，因此不会影响上凸壳的完整性
    因此可以直接O(1)插入即可
    然后查询的话，凸包满足三分性质，直接三分
    复杂度O(n log n)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=100005;
struct node {long long a,x;} a[N];
int n,stack[N],top,tot; long long d,sum[N]; double ans;
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;
}
void init()
{
    n=getint(); d=getint();
    for (int i=1; i<=n; i++) a[i].a=getint(),a[i].x=getint();
    for (int i=1; i<=n; i++) sum[i]=sum[i-1]+a[i].a;
}
void ask(long long now,long long x)
{
    int l=1,r=tot; double nowans=0;
    while (l<=r)
    {
        int len=(r-l)/3,mid=l+len,Mid=r-len;
        long long x1=(now-stack[mid])*d+x,y1=sum[now]-sum[stack[mid]-1];
        long long x2=(now-stack[Mid])*d+x,y2=sum[now]-sum[stack[Mid]-1];
        double val=(double)y1/x1,Val=(double)y2/x2;
        if (val>Val) {nowans=max(nowans,val); r=Mid-1;}
        else {nowans=max(nowans,Val); l=mid+1;}
    }
    ans+=nowans;
}
void solve()
{
    tot=0; ans=0;
    for (int i=1; i<=n; i++)
    {
        while (tot>1)
        {
            long long x1=(i-stack[tot-1])*d+a[i].x,y1=sum[i]-sum[stack[tot-1]-1];
            long long x2=(i-stack[tot])*d+a[i].x,y2=sum[i]-sum[stack[tot]-1];
            long long x3=a[i].x,y3=a[i].a;
            long long X1=x2-x3,Y1=y2-y3;
            long long X2=x1-x2,Y2=y1-y2;
            if (X1*Y2-X2*Y1>0) {tot--; continue;} break;
        }
        stack[++tot]=i; ask(i,a[i].x);
    }
    printf("%.0lf\n",ans);
}
int main()
{
    init();
    solve();
    return 0;
}