给定 \(n\) 个数 \(h_{1 \dots n}\)。
你需要进行 \(m\) 轮操作，每轮操作为 \(k\) 次修改，每次修改可以选择一个数 \(h_i\) 修改为 \(\max(h_i - p, 0)\)。
每轮操作后每个 \(h_i\) 将会被修改为 \(h_i + a_i\)。
你需要最小化最终 \(h_{1 \cdots n}\) 中的最大值。
\(n \le 10^5\)，\(m \le 5 \times 10^3\)，\(k \le 10\)。
二分答案，考虑如何 check。
正着做要考虑对 0 取 max，比较麻烦，所以可以时光倒流。然后问题就变成了初始有 \(n\) 个数，每个都是 \(mid\)，每个时刻第 \(i\) 个会减少 \(a_i\)，你每个时刻可以进行 \(k\) 次操作，每次操作是选一个数让他加 \(p\)，求能不能在 \(m\) 个时刻后让每个数都大于等于 \(h_i\)，还要保证每个时刻数都非负。
这个可以贪心地去做，按还剩多少天减成负数维护一个堆，然后每次取出堆顶，对他操作一次，最后判断堆是否为空就行。
时间复杂度 \(O((n + mk) \log n\)。
constexpr int MAXN = 1e5 + 9, MAXM = 5e3 + 9, MAXK = 11;
int n, m, k, p, h[MAXN], a[MAXN], cnt[MAXN];
bool check(ll x) {
priority_queue<pli, vector<pli>, greater<pli> > q;
for (int i = 1; i <= n; i ++) {
if (x - 1ll * m * a[i] >= h[i]) continue;
q.emplace(x / a[i], i), cnt[i] = 0;
}
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= k; j ++) {
if (q.empty()) return true;
auto [day, id] = q.top(); q.pop();
if (day < i) return false; cnt[id] ++;
day = (x + 1ll * p * cnt[id]) / a[id];
if (x - 1ll * a[id] * m + 1ll * p * cnt[id] < h[id])
q.emplace(day, id);
}
if (q.size()) return false;
else return true;
}
void slv() {
n = Read<int>(), m = Read<int>(), k = Read<int>(), p = Read<int>();
for (int i = 1; i <= n; i ++) h[i] = Read<int>(), a[i] = Read<int>();
ll l = 0, r = 1e13;
while (l < r) {
ll mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
Write(l, '\n');
return;
}