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 secunda $0$.
* Din fiecare seif $i$ se poate lua o sumă de bani *egală* cu $b[i]$.

* 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.

h2. Date de intrare

Fişierul de intrare $spargere.in$ conţine pe prima linie numărul $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ă.

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

* $1 ≤ N ≤ 100$
* $1 ≤ b[i], t[i] ≤ 1.000$

* $1 ≤ Q ≤ 1.000$

* $1 ≤ Q ≤ 100.000$

* $1 ≤ X ≤ 1.000.000.000$

* $Numerotarea secundelor se face începând cu secunda 0.$

h2. Exemplu
table(example). |_. spargere.in |_. spargere.out |

| 2
2 1
3 2
2
1
11
| 0
2

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

În secunda $0$, se vor lua bani din ambele seifuri. În total, vom avea $5$ bani. Primul seif se va deschide din nou în secunda $1$, iar cel de-al doilea în secunda $2$. În secunda $1$, vom lua din nou bani din primul seif. În total, vom avea $7$ bani. Acesta se va deschide din nou în secunda $2$. În secunda $2$, vom lua bani din ambele seifuri. În total, vom avea $12$ bani. Deci, în două secunde, avem cel puţin $11$ bani.

...

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

9722