New York

După ce ai devenit cel mai renumit om de afaceri din Europa, te-ai mutat în New York și dorești să le arăți și americanilor că ești cel mai tare din parcare. Strategia care ți-a adus ție tot succesul este următoarea: cumperi o clădire, o renovezi, iar apoi o vinzi la un preț mai mare.

Există $N$ clădiri la vânzare. Clădirea $i$ costă $a_i$ dolari, dar în urma calculelor tale, dacă o renovezi și o vinzi ulterior poți obține $b_i$ dolari profit.

O clădire poate fi cumpărată cel mult o dată (deoarece nu ai mai avea ce să renovezi a doua oară), iar ele pot fi cumpărate și vândute în orice ordine.

De asemenea, niciodată nu ai voie să ai un număr negativ de dolari în cont, deci pentru a cumpăra a $i$-a clădire, trebuie să ai cel puțin $a_i$ dolari la momentul achiziționării.

Atenție! NU vinzi clădirea cu $b_i$ dolari, ci câștigi $b_i$ dolari (de fapt o vinzi pentru $a_i + b_i$) dolari.

Cerință

După o cercetare atentă, ai identificat $N$ clădiri care ar putea duce la un profit. Încă nu știi exact cât de costisitor va fi să te muți în New York, așadar îți pui $Q$ întrebări de forma: Dacă aș ajunge cu $T$ dolari, care e averea maximă (în dolari) pe care aș putea să o dețin la sosirea din New York?

Date de intrare

Pe prima linie se află numărul $N$, reprezentând numărul de clădiri care ți-ar putea aduce un eventual profit.

Pe linia $i + 1$ ($1 \leq i \leq N$) se află valorile $a_i$ și $b_i$, în această ordine.

Pe linia $N + 2$ se află numărul $Q$, reprezentând numărul de întrebări.

Pe fiecare dintre următoarele $Q$ linii se află câte un întreg $T$, reprezentând numărul inițial de dolari.

Date de ieșire

Se vor afișa $Q$ linii. Pe a $i$-a linie se va afla răspunsul la a $i$-a întrebare.

Restricții și precizări

$\textcolor{red}{Atenție!}$ Din cauza numărului mare de date de intrare, respectiv ieșire, vă recomandăm să adăugați următoarele linii de cod la începutul funcției main().

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

• $1 \leq N \leq 200 \ 000$
• $1 \leq Q \leq 1 \ 000 \ 000$
• $1 \leq a_i, b_i \leq 10^9$
• $1 \leq T \leq 10^9$

Exemplul 1

stdin

3
3 4
1 1
9 6
10
1 2 3 4 5 6 7 8 9 10 

stdout

2
7
8
15
16
17
18
19
20
21

Explicație

$T = 1$: Pot cumpăra și renova clădirea $2$. Pot deoarece $a_2 = 1$, deci $T \geq a_2$. Inițial aveam un dolar, iar acum am $1 + b_2 = 1 + 1 = 2$

$T = 2$: Inițial, cumpăr și renovez clădirea $2$. Acum, am $3$ dolari, deci pot cumpăra și clădirea $1$. După ce vând clădirea $1$ voi avea $3 + 4 = 7$ dolari.

$T = 3$: Similar cu $T = 2$, voi cumpăra clădirile $2$ și $1$ în ordinea aceasta. Voi avea $3 + 1 + 4 = 8$ dolari.

$T = 4$: După ce cumpăr clădiriile $2, 1$ am $9$ dolari. Astfel pot cumpăra clădirea $3$, iar în final voi avea $4 + 1 + 4 + 6 = 15$ dolari.