== include(page="template/taskheader" task_id="spargere") ==

Georgică a terminat cu progresiile aritmetice şi si-a găsit o nouă ocupaţie: s-a decis să devină un spărgător profesionist. Primul pas în această carieră este spargerea seifurilor băncii Georgelonia. Banca are $N$ seifuri, iar fiecare dintre acestea conţine o sumă infinită de bani.

Georgică a terminat cu progresiile aritmetice şi si-a găsit o nouă ocupaţie: s-a decis să devină un spărgător profesionist. Primul pas în această carieră este spargerea seifurilor băncii Georgelonia. Banca are $N$ seifuri, iar fiecare dintre acestea conţine o sumă infinită de bani. Pentru a nu declanşa alarma, Georgică trebuie să respecte următoarele reguli:
 
* Toate seifurile sunt deschise în cu secunda $0$.
* Din fiecare seif $i$ se poate lua doar o sumă de bani egală cu $b[i]$.
* Fiecare seif $i$ se va închide în momentul în care suma de bani este luată din el. Acesta se va deschide din nou peste exact $t[i]$ secunde.
* Georgică poate lua bani din oricâte seifuri doreşte într-o secundă, condiţia fiind ca acestea să fie deschise.
 
De exemplu, dacă Georgică ia bani din seiful $i$ la secunda $T$, acesta se va închide, urmând să se deschidă în secunda $T + t[i]$.
 
Pentru a se asigura că este un spărgător bun, Georgică trebuie să răspundă la $Q$ întrebări de tipul:
 
* Care este timpul minim în care poţi obţine o sumă de bani mai mare sau egală decât $X$?
 
Ajutaţi-l pe Georgică să devină un spărgător profesionist, răspunzând la întrebări!

h2. Date de intrare

Fişierul de intrare $spargere.in$ ...

Fişierul de intrare $spargere.in$ conţine pe prima linie numărul natural $N$. Pe următoarele $N$ linii, se găsesc două numere naturale $b[i]$ şi $t[i]$, având semnificaţia din enunţ. Pe linia următoare, se găseşte numărul natural $Q$, iar pe urmatoarele $Q$ linii se găseşte câte un număr $X$, reprezentând o întrebare pusă lui Georgică.

h2. Date de ieşire

În fişierul de ieşire $spargere.out$ ...

În fişierul de ieşire $spargere.out$ se vor găsi $Q$ linii, fiecare linie $i$ conţinând un singur număr, reprezentând răspunsul la întrebarea $i$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100$
* $1 ≤ b[i], t[i] ≤ 1.000$
* $1 ≤ Q ≤ 100.000$
* $1 ≤ X ≤ 1.000.000.000$

h2. Exemplu