题目描述

美术馆有n幅画，在画廊里从西向东排成一列，这些画从西向东编号为1∼n。第i幅画在距离最西端$x_i$米位置，它的价值为$v_i$。

明天要召开展览会，来客会非常多，馆长决定只展出其中m幅画，其他画都拿走放到库房里。如果留下的画距离太近，观众们观赏起来会不方便。所以留下的画之间的距离必须大于等于D。

展览会的“华丽度”定义为展出的m幅画中，价值最低的画的价值。通过适当选择留下的m幅画，能得到最大的“华丽度”是多少。

输入格式

第1行，3个正整数n,m,D

接下来n行，每行两个整数$x_i$,$v_i$

输出格式

输出可以得到的最大“华丽度”。如果无法选出满足要求的画，输出−1。

样例输入

3 2 20
10 250
30 200
50 500

样例输出

250

提示

样例1说明：留下第1、3幅画，“华丽度”等于其中较小的价值250。

前20%数据：$n\le 15$

前40%数据：$n\le 1000$

另有10%数据：$m=1$或$m=n$

100%数据：$n\le 10^{5}$；$1\le m\le n$；$1\le D,x_i,v_i\le 10^{9}$；$x_i$互不相同。

3 1 4
4 9
5 1
9 5

9

3 1 4 
4 9 
5 1 
9 5

9

3 1 4  
4 9  
5 1  
9 5

9