RNE 엔터테인먼트에서 새로운 가수 그룹을 결성하려고 한다. 한편, 이 소식을 듣고 N명의 지원자가 오디션을 보았다. RNE 엔터테인먼트의 수장인 승현이는 각 지원자가 노래를 부르면서 실수를 한 횟수를 센 후 노래의 난이도를 나눠서 각 지원자의 노래 실력 Sk를 매겼다. 한편, 승현이는 각 지원자가 오디션을 보는 사이에 그들의 외모 점수 Vk를 매겼다. 승현이의 독특한 점수 환산 방식 때문에, 노래를 매우 잘 부르면서 매우 잘생긴 지원자의 경우에는 Sk가 낮게 나오고 Vk가 높게 나올 것이다.

하지만 대중은 가수를 볼 때 가창력은 별로 보지 않고 외모만을 보는 경향이 있기 때문에, 승현이가 최종적으로 선발한 멤버들은 외모 점수의 합이 최대가 되어야 한다. 그런데, 잘생긴 정도가 너무 비슷한 두 멤버가 있으면 팬들끼리 다툼이 일어나기 때문에, 잘생긴 정도가 비슷한 두 멤버는 동시에 그룹에 넣을 수 없다. 여기에서, A, B의 잘생긴 정도가 비슷하다는 말은, 외모 점수가 A와 B 사이에 있는 다른 지원자 C가 없다는 말과 같다.

승현이는 자신이 키운 그룹의 어떤 멤버가 노래를 못 한다는 말을 듣기 싫어하므로, 노래 실력이 SM 이하인 지원자들만 뽑을 것이다. 한편, 그룹에 너무 멤버가 많으면 멤버들을 관리하기 힘드므로, 뽑는 멤버의 수는 최대 KM이다. 승현이는 자신이 SM과 KM을 정하면서, 자신이 만들게 되는 그룹(사실, 그룹까지는 아닐 수 있다)이 어떻게 될지 알고 싶어 한다. 승현이가 만들게 되는 그룹에서, 멤버들의 외모 점수의 합을 구하는 프로그램을 작성하여라.

예제 설명

⑴ 1, 3, 6번째 지원자를 뽑으면 된다.
⑵ 1, 5번째 지원자를 뽑으면 된다. 2번째 지원자와 5번째 지원자는 잘생긴 정도가 비슷하기 때문에 같이 뽑을 수 없다.
⑶ 1, 3, 5, 6번째 지원자를 뽑으면 된다. 5명을 뽑을 수 있는 방법이 없으므로 4명을 뽑게 된다.
⑷ 노래 실력이 10 이하인 지원자가 없으므로 승현이가 그룹을 만들 수 없다.

입력

• 첫 번째 줄에는 지원자의 수 N이 주어진다.
• 두 번째 줄부터 N개의 줄에는 각 지원자의 노래 점수 Sk와 외모 점수 Vk가 주어진다. 노래 점수와 외모 점수는 1,000,000,000 이하이다.
• N+2번째 줄에는 승현이가 궁금해 하는 조합의 수 Q가 주어진다.
• N+3번째 줄부터 Q개의 줄에는 노래 실력의 상한값 SM과 뽑을 수 있는 최대 멤버 수 KM이 주어진다.

출력

입출력 예

입력

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

출처 : Balkan Olympiad in Informatics 2012, Day 2 Task 2
http://boi2012.dms.rs/index.php?action=show&data=tasks
번역: functionx