小K的花园种着n颗竹子（竹子是一种茎部中空并且长得又高又快的热带植物）。此时，花园中第i颗竹子的高度是hi米，并且在每天结束的时候它生长ai米。
实际上，小K十分讨厌这些竹子。他曾经试图去砍光它们，但由于竹子的茎部太坚固而失败了，然而，小K制作了魔法锤使这些竹子只能在地面上生长。
由于魔法力量有限，他每天最多能使用K次魔法锤。每次他使用魔法锤敲击竹子，竹子的高度就会减少p米。通过这次改变，如果竹子的高度变为负数，那它转而会变为0米（但它不会消失）。换言之，如果一颗被魔法锤敲击的竹子的高度是h，那它的新高度将会是max(0, h - p)米。我们可以在一天中多次敲击同一颗竹子。
小K将会从今天开始和这些竹子抗战m天。他的目标是在m天后使其中最高的竹子的高度最小化（即，“小K敲击竹子，然后竹子生长”的m次迭代）。找出m天后，最高的竹子的高度的最小可能值。
Input
输入的第一行包含四个以空格隔开的整数n，m，k和p(1 ≤ n ≤ 10^5 ,1 ≤ m ≤ 5000, 1 ≤k≤ 10, 1 ≤ p ≤ 10^9)。它们分别表示小K 花园中的竹子数，小K抗战的持续天数，每天小K能敲击竹子的最多次数和魔法锤的力量。
接下来n行描述了竹子的特性，第i行(1 ≤ i ≤ n) 包含两个以空格隔开的整数hi和ai，(0 ≤ hi ≤ 10^9, 1 ≤ ai ≤ 10^9)，分别表示第i颗竹子的初始高度和生长速率。
Output
输出m天后，最高的竹子的高度的最小可能值。
跑去看了cf官网的题解。。
先二分，判定是否可行的时候可以时光倒流。假设最后所有竹子的高度都是二分的答案mid，倒着过去每天，竹子就会变矮p米，不能让竹子的高度变成负数，魔法锤变成给竹子加高度。最后只要使所有竹子高度>=实际初始高度就好了。
每次用魔法锤的时候，如果存在竹子再过一些天高度就变负数的话，就用在变负天数最少的竹子上。不然就用在最后和实际初始高度差最大的竹子上。用个堆维护一下。
复杂度两个log
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define d double
#define ld long double
const int maxn=; struct zs{int id;ll h,tim;};std::priority_queue<zs>q;
struct zsa{ll h,v;}a[maxn];
int i,j,k,n,m,kk,p; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while(rx<''&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>='')ra=ra*+rx-,rx=getchar();return ra*fh;
} bool operator <(zs a,zs b){return a.tim>b.tim;}
inline bool check(ll X){
register int i;int tim;zs now;
while(!q.empty())
q.pop();
//printf("mid:%lld\n",X);
for(i=;i<=n;i++)if(X<a[i].v*m+a[i].h)
q.push((zs){i,X,X/a[i].v+});//,printf(" %d\n",i);
for(i=;i<=kk*m&&!q.empty();i++){
tim=(i+kk-)/kk,
now=q.top(),q.pop();
if(now.tim<=tim)return ;
now.h+=p,now.tim=now.h/a[now.id].v+;
if(now.h<a[now.id].v*m+a[now.id].h)q.push(now);
}
return q.empty();
}
inline ll max(ll a,ll b){return a>b?a:b;}
int main(){
n=read(),m=read(),kk=read(),p=read();
ll l=,r=,mid;
for(i=;i<=n;i++)a[i].h=read(),a[i].v=read(),r=max(r,a[i].h+m*a[i].v); while(l<r){//printf(" %lld %lld\n",l,r);
if(check(mid=l+r>>))r=mid;else l=mid+;
}
printf("%lld\n",l);
}