题目描述

本题译自 eJOI2021 Problem F. Waterfront

普洛耶什蒂（Ploiești）市市长在普拉霍瓦河（Prahova River）畔种了一排 $N$ 棵不同品种的观赏性灌木。每棵灌木初始高度为 $h_i$。根据种植的土壤条件和天气状态，第 $i$ 棵灌木每天生长的高度为 $d_i$。

每天，市政厅的园丁都会通过用剪刀修建灌木来调整这些灌木的高度。然而，园丁被剪刀的质量所限制。因此对于一次修剪，如果这棵灌木至少 $x$ 厘米高，那么园丁可以恰好从这棵灌木剪下 $x$ 厘米的高度（注意剪完之后灌木的高度可以为 $0$）。为了不会很累，园丁一天可以进行最多 $k$ 次修剪。在一天里园丁可以对同一灌木修剪多次。

市长会在 $M$ 天后组织一次艺术活动，他希望知道在 $M$ 天后最高的灌木最矮可能是多高。

注意：对于每天，树先生长，然后进行修剪。

输入格式

第一行四个整数 $N,M,k,x$。

接下来 $N$ 行，每行两个整数 $h_i,d_i$。

输出格式

输出一个非负整数，表示 $M$ 天后最高的灌木最矮可能的高度。

4 3 4 3
2 5
3 2
0 4
2 8

8

数据范围与提示

• $1\le k\le 1000$
• $1\le x\le 10^4$
• $0\le h_i\le 10^4$
• $0\le d_i\le 10^4$