题目名称

组队竞赛

题目描述

有 $n$ 位同学想要参加小爱组建的信息学竞赛队伍，每位同学都有对应的能力值 $a_i$ 与热情度 $b_i$ 。小爱认为，若队伍中能力值最大的选手与能力值最小的选手之间的差值大于给定的 $X$ ，会因能力差距过大而不利于团队学习与凝聚力。请帮助小爱找出一种选择队伍选手的方案，使得所选选手的能力值差值不超过 $X$ ，且总热情度最大。

输入格式

1. 第一行输入一个正整数 $n$，代表选手的数量。
2. 接下来 $n$ 行，每行输入两个正整数 $a_i, b_i$，分别表示每位选手的能力值和热情度。
3. 最后一行输入一个正整数 $X$，表示小爱期望的能力值差值上限。

输出格式

输出一个整数，即满足能力值差值条件下的最大总热情度。

数据范围

• 对于 $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$ 。

输入输出样例

输入样例

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

输出样例

170

样例解释

选择第3、4、5个选手。他们的能力值分别为30、40、50 ，能力值差值为 $50 - 30 = 20$，未超过给定的能力值差值上限20 。此时总热情度为 $27 + 89 + 54 = 170$ 。