DMPG '17 B5 - Hackathons

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Python 3.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Roger is going to a hackathon again! Unlike last time, he has prepared a possible list of projects and has an estimate of how long each project takes, as well as its wow factor. However, his partner, Joey, wishes to go for very long coffee breaks, and thus gives him queries to answer: if they only have minutes to complete their project, what is the maximum wow factor of their project.

Note: at hackathons (or at least the ones in this question), only a single project is done.

Input Specification

Line : An integer, , the number of projects Roger has prepared.
Lines : Two space separated integers, , and , the amount of time required for the project and its wow factor respectively.
Line : An integer, , the number of queries Joey gives.
Line : An integer, , the maximum time Roger and Joey have.

Output Specification

space-separated integers, the answer to each query.

Sample Input

3
1 3
8 9
2 2
3
10
8
3

Sample Output

9
9
3

Explanation for Sample Output

If Roger and Joey have minutes, they have enough time to complete projects , , and , and the maximum wow factor is .
If they have minutes, they still have time to complete all three projects, so the maximum wow factor is still .
If they have minutes, they can only complete projects and , and the maximum wow factor of these two projects is .