运输机从天边坠落，一道火花从天幕中划过...

机体展开翅膀，缓缓飞到教堂上方。她手里握着赫斯提亚，身后飞着僚机，发出一束强光...

那是极昼...

教堂前一共有 n 只感染体。第 i 只感染体位于坐标 x_i 的位置，生命为 h_i。

丽芙现在要释放技能“终末祈愿”来击毁这 n 只感染体。在点 x 放一次技能可以使坐标 [x - d] 到 [x + d] 的这个区间内的所有感染体减去 k 点生命。当一只感染体的生命值 ≤ 0 时，这只感染体就被摧毁了。

但是极昼机体的能量有限，最多只能发动 m 次技能。求攻击半径 d 的最小值。

第一行，三个正整数 n, m, k，分别为感染体的数量，允许攻击的次数和一次攻击的伤害。

接下来有 n 行，每行两个整数 x_i, h_i 分别为第 i 只感染体的位置和生命。

一行一个整数为答案。

1 ≤ n ≤ 10 ^ 5

1 ≤ x_i ≤ 10 ^ 9