1.算法:

二分+贪心

2.思路:

首先我们二分出一个值x,对于这个值就行check...怎么check呢?
一个很显然的东西,假如我的开始值是x,且我x-a[i]*m>=h[i]这种值是不可能用到的.
其次我们假设我们的初始值是x,且都要用到,那么我肯定是选变成负数步数最少的优先,因为我想让我每次减少的p尽可能的多.
然后就可以直接用优先队列模拟维护了.

3.代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
ll a[N],h[N];
ll n,m,k,p;
struct Q{
    ll tot,ai,num,id;
    friend bool operator<(const Q &A,const Q &B)
    {
        return A.num>B.num;
    }
};
bool check(ll x)//枚举那个最大值最小的值并验证是不是可行.
{
    priority_queue<Q>q;
    for(int i=1;i<=n;i++)
    {
        if(x-a[i]*m<h[i])    q.push({x,a[i],(x)/a[i],i});
    }
    for(int i=1;i<=m&&q.size();i++)//m轮
    {
        for(int j=1;j<=k&&q.size();j++)//k次抬高
        {
            auto temp=q.top();q.pop();
            int id=temp.id;
            if(temp.tot-temp.ai*i<0)    return false;
            temp.tot+=p;temp.num=(temp.tot)/temp.ai;
            if(temp.tot-temp.ai*m<h[id])    q.push(temp);
        }
    }
    while(q.size())
    {
        auto temp=q.top();
        q.pop();int id=temp.id;
        if(temp.tot-temp.ai*m<h[id])    return false;
    }
    return true;
}

int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
    for(int i=1;i<=n;i++)    scanf("%lld%lld",&h[i],&a[i]);
    ll l=1,r=1e18,ans=1e18;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid))
        {
            r=mid-1;
            ans=min(ans,mid);
        }
        else
        {
            l=mid+1;
        }
    }printf("%lld\n",ans);
    return 0;
}