问题 6112 --组队竞赛

6112: 组队竞赛

题目描述

有$n$同学想要参加小爱组建的一支信息学竞赛队伍,每位同学有能力值$a_i$与热情度$b_i$。 小爱认为,如果队伍当中,能力值最大与能力值最小选手之间,能力差值大于给定$X$,会导致能力差距过大、不利于团队的学习与凝聚力。因此,请你帮助小爱计算下,如何选择队伍的选手,才能使所有选手的能力差值小于等于$X$,且热情度最大。

输入

输入第一行,一个正整数$n$,表示有$n$位选手 接下来$n$行,每行两个正整数$a_i,b_i$表示每位选手的能力值与热情度。 最后一行,一个正整数$X$,表示小爱希望的能力差值上限

输出

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

样例输入输出

输入#1 复制
5
10 21
20 34
30 27
40 89
50 54
20
输出#1 复制
170

提示

- 对于$30\%$的数据,$1 \leq n \leq 100$ - 对于$60\%$的数据,$1 \leq n \leq 10^4$ - 对于$100\%$的数据,$1 \leq n \leq 10^5,1 \leq x \leq 10^9,1 \leq a_i,b_i \leq 10^9$ 样例1说明:选第3、4、5个选手。 能力值分别为30、40、50,不超过50-30=20给定的能力差值上限20 此时热情度为27+89+54=170
序号 标题 作者 发表时间 费用 订购数 操作