观察到如果有减的时候减成负数了的情况很难处理
于是我们让时间倒流过来
本来砍掉他就相当于是把他拔高多少 本来每天长高多少就相当于是每天自己缩回去多少
于是二分答案所有竹子最后都高为\(x\) 看它在这么多天结束后会不会缩到比\(h_i\)更小的地方去
如果小了 就代表这个\(x\)太矮了 有竹子最后会超出这个\(x\)
但是在拔高的过程中我们不允许有负数出现（不然就砍过头了 违反了砍成负数变成0的规则）
所以每次拔那些快变成负数的竹子（如果有来不及拔的就说明满足不了了 return 0）
最后看是不是所有数都满足大于等于\(h_i\)的条件 满足就return 1
做的时候用一个小根堆即可
#include<bits/stdc++.h>
using namespace std;#define int long long
#define endl '\n'const int N=1e5+10;int n,m,k,p;
int h[N],a[N];
int c[N];//记录每棵竹子已经被加的次数
int l,r;
int ans=-1;struct node{int cnt,id;//可以坚持的天数 编号
};
bool operator < (const node a,const node b){return a.cnt>b.cnt;
}int check(int x){priority_queue<node>q;memset(c,0,sizeof(c));for(int i=1;i<=n;i++){if(h[i]+a[i]*m>x)q.push({x/a[i],i});}for(int i=1;i<=m;i++){for(int j=1;j<=k&&(!q.empty());j++){node top=q.top();q.pop();int cnt=top.cnt;int id=top.id;if(cnt<i)return 0;c[id]++;if(x+c[id]*p<h[id]+a[id]*m){q.push({(x+c[id]*p)/a[id],id});}}}if(q.empty())return 1;else return 0;
}signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m>>k>>p;for(int i=1;i<=n;i++){cin>>h[i]>>a[i];r=max(r,h[i]+a[i]*m);}l=0;while(l<=r){int mid=(l+r)>>1;if(check(mid)){ans=mid;r=mid-1;}else{l=mid+1;}}cout<<ans<<endl;return 0;
}