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 
~Q~ queries to answer: if they only have 
~T~ 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.
Constraints
For all subtasks:
~1 \le t_i, w_i, T \le 10^6~
Subtask 1 [60%]
~1 \le N, Q \le 10^3~
Subtask 2 [40%]
~1 \le N, Q \le 10^6~
Input Specification
Line 
~1~: An integer, 
~N~, the number of projects Roger has prepared.
Lines 
~2 \dots N+1~: Two space separated integers, 
~t_i~ and 
~w_i~, the amount of time required for the 
~i^{th}~ project and its wow factor respectively.
Line 
~N+2~: An integer, ~Q~, the number of queries Joey gives.
Lines 
~N+3 \dots N+Q+2~: An integer, ~T~, the maximum time Roger and Joey have.
Output Specification
~Q~ 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 
~10~ minutes, they have enough time to complete projects ~1~, 
~2~, and 
~3~, and the maximum wow factor is 
~9~.
If they have 
~8~ minutes, they still have time to complete all three projects, so the maximum wow factor is still ~9~.
If they have ~3~ minutes, they can only complete projects ~1~ and ~3~, and the maximum wow factor of these two projects is ~3~.
Comments
I believe fast I/O is necessary for this problem
This comment is hidden due to too much negative feedback. Show it anyway.
Note: at hackathons (or at least the ones in this question), only a single project is done.
they have enough time to complete projects 1, 2, and 3.
I am actually really confused right now. Are they doing multiple projects like the example, or a single project?
EDIT: oh wait never mind, I see what happens now