#include<bits/stdc++.h> #define FILE "plant" #define MAXN 100010 #define eps 1e-7 using namespace std; typedef long long ll; struct node{ ll x,y; node(){} node(const ll a,const ll b):x(a),y(b){} }p[MAXN],sta[MAXN]; int n,top; ll d,a[MAXN],sum[MAXN]; double ans; inline ll read(){ ll x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } double slop(node a,node b){return (double)(a.y-b.y)/(a.x-b.x);} void insert(const node &b){ while(top>=2&&slop(sta[top-1],sta[top])>=slop(sta[top],b)-eps) --top; sta[++top]=b; } double find(node b){ int l=1,r=top; double temp=0; while(l+3<=r){ int mid1=(r-l)/3+l,mid2=(r-l)*2/3+l; if(slop(sta[mid1],b)>slop(sta[mid2],b)) r=mid2; else l=mid1; } for(int i=l;i<=r;++i) temp=max(temp,slop(sta[i],b)); return temp; } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read(); d=read(); for(int i=1;i<=n;++i){ a[i]=read(); sum[i]=sum[i-1]+a[i]; ll x=read(); insert(node(d*i,sum[i-1])); ans+=find(node(d*i+x,sum[i])); } printf("%.0lf\n",ans); return 0; }
|