#P3022. [Balkan2012]The Best Teams
[Balkan2012]The Best Teams
[BalkanOI 2012] The Best Teams
题目描述
选拔员 Srba 要为 BOlympic Games 2012 的每场比赛组建队伍。他有 名选手可供选择,并知道每名选手的年龄和能力值。队伍的能力值为所有入选选手的能力值之和。
能力相近的选手不能同时入选。所有选手的能力值互不相同。若没有第三名选手的能力值严格介于两名选手之间,则这两名选手能力相近。用全部 名选手按能力值排序,能力相近的选手正好是排序后相邻的选手。
共有 场比赛。每场比赛有年龄上限 和队员人数上限 。队伍中每名选手的年龄都不得超过 ,人数不得超过 。各场比赛独立选人,同一名选手可以参加多场比赛。
对每场比赛,求组出的队伍的最大能力值。空队伍的能力值为 。
输入格式
第一行一个整数 。接下来 行,第 行包含两个整数 ,分别表示第 名选手的年龄和能力值。
随后一行一个整数 。接下来 行,第 行包含两个整数 ,分别表示第 场比赛的年龄上限和人数上限。
输出格式
输出 行,按输入顺序逐场输出队伍的最大能力值。请使用 位整数。
数据范围
,,所有选手的能力值互不相同。
- 的测试满足 。
样例
7
17 21
24 36
14 19
27 20
21 50
18 5
33 7
4
20 3
50 2
99 5
10 2
45
71
95
0
样例解释
能力相近的选手对为 。前三场比赛各自的最优队伍依次为 、、。第四场比赛的年龄上限为 ,没有选手符合要求。