看到陈指导写的标签就直接知道怎么做了，想到倒着做还是比较简单的
首先最大值最小我们一眼二分答案(x)，然后我们就发现那个(max(h_i-p,0))很难处理
考虑倒着做，这样操作就变成了：
- 初始时每个数都是(x)
- 做(k)次，每次选择一个数加上(p)
- 将所有数减去(a_i)
最后要求做的过程中所有数都要大于等于(0)并且最后要超过(h_i)
思考如何检验，我们发现此时我们可以把增加的操作攒起来一起加
容易想到我们可以开一个桶，分别记录做(i)次操作后哪些位置会小于(0)
枚举减的操作次数，将对应的桶内的元素需要的加上次数累加后重新计算扔进桶里即可
由于加数操作在第(i)次不能超过(i imes k)，因此检验一次复杂度就是(O(n+mk))的
综上，总复杂度(O((n+mk)log (p imes m)))
#include<cstdio>
#include<vector>
#define RI register int
#define CI const int&
#define int long long
using namespace std;
typedef vector <int>:: iterator VI;
const int N=100005,M=5005;
int n,m,k,p,h[N],a[N],s[N],ans; vector <int> v[M];
inline void expand(CI x,CI y)
{
if (x<m) v[x].push_back(y);
}
inline bool check(CI x)
{
RI i; int sum=0; for (i=1;i<=m;++i) v[i].clear();
for (i=1;i<=n;++i) expand((s[i]=x)/a[i],i);
for (i=0;i<m;++i) for (VI it=v[i].begin();it!=v[i].end();++it)
{
int dlt=(a[*it]*(i+1)-s[*it]+p-1)/p;
if (s[*it]+=dlt*p,(sum+=dlt)>i*k) return 0; expand(s[*it]/a[*it],*it);
}
for (i=1;i<=n;++i) if (s[i]<a[i]*m+h[i])
if ((sum+=(a[i]*m+h[i]-s[i]+p-1)/p)>m*k) return 0; return 1;
}
signed main()
{
RI i; for (scanf("%lld%lld%lld%lld",&n,&m,&k,&p),i=1;i<=n;++i)
scanf("%lld%lld",&h[i],&a[i]); int l=1,r=1e15,mid; while (l<=r)
if (check(mid=l+r>>1)) ans=mid,r=mid-1; else l=mid+1;
return printf("%lld",ans),0;
}