1642:组队竞赛

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判 命题人:
提交:11 解决:3

题目描述

lns="http://www.w3.org/1998/Math/MathML">同学想要参加小爱组建的一支信息学竞赛队伍,每位同学有能力值lns="http://www.w3.org/1998/Math/MathML">与热情度lns="http://www.w3.org/1998/Math/MathML">

小爱认为,如果队伍当中,能力值最大与能力值最小选手之间,能力差值大于给定lns="http://www.w3.org/1998/Math/MathML">,会导致能力差距过大、不利于团队的学习与凝聚力。因此,请你帮助小爱计算下,如何选择队伍的选手,才能使所有选手的能力差值小于等于lns="http://www.w3.org/1998/Math/MathML">,且热情度最大。


输入

输入第一行,一个正整数lns="http://www.w3.org/1998/Math/MathML">,表示有lns="http://www.w3.org/1998/Math/MathML">位选手
接下来lns="http://www.w3.org/1998/Math/MathML">行,每行两个正整数 lns="http://www.w3.org/1998/Math/MathML">, 表示每位选手的能力值与热情度。
最后一行,一个正整数 ,表示小爱希望的能力差值上限  

1≤n≤105,1≤x≤109,1≤ai,bi≤109

输出

输出一个整数,表示满足条件的情况下,最大热情度的值

样例输入-1 复制

5
10 21
20 34
30 27
40 89
50 54
20

样例输出-1 复制

170