题目描述

给定 $n$ 个数 $h_1 \dots h_n$。你需要进行 $m$ 轮操作，每轮操作为 $k$ 次修改，每次修改可以选择一个数 $h_i$ 修改为 $\max(h_i - p, 0)$。每轮操作后每个 $h_i$ 将会被修改为 $h_i + a_i$。

你需要最小化最终 $h_{1 \dots n}$ 中的最大值。

$n \le 10^5$，$m \le 5 \times 10^3$，$k \le 10$，$1\le p\le 10^{9}$，$0\le h_{i}\le 10^{9}$，$1\le a_{i}\le 10^{9}$。

输入格式

第一行四个整数 $n,m,k,p$。

接下来 $n$ 行每行两个整数 $h_i, a_i$。

输出格式

一个整数表示答案。

3 1 2 5
10 10
10 10
15 2

17

2 10 10 1000000000
0 10
0 10

10

5 3 3 10
9 5
9 2
4 7
9 10
3 8

14