U jednom malom gradiću uz more nalazi se autobusni kolodvor. Zaposlenici tog kolodvora su jako lijeni i žele cijeli dan piti kavu.

Međutim, baš je danas kolodvor pretrpan i na njemu se trenutno nalazi N grupa putnika. Članovi svake grupe su jako bliski, pa žele krenuti istovremeno. Zaposlenici su odlučili smanjiti gužvu, pa su svakoj grupi dali redne brojeve po kojima kreću. Dakle, grupe su označene brojevima od 1 do N i to je redoslijed njihovog odlaska. Prvo odlazi prva grupa, pa zatim druga itd.

Zaposlenicima je poznat i raspored dolazaka autobusa na kolodvor, odnosno znaju za koliko minuta će doći koji autobus i koliko mjesta ima u njemu. Nakon što dođu, autobusi s kolodvora kreću na vrlo specifičan način. Svaki autobus može krenuti tek nakon što je cijela grupa na redu za odlazak ušla u autobuse.

Dakle, prva grupa čeka dovoljan broj autobusa u koji može stati. I tek kad svi (iz prve grupe) stanu u x autobusa, svi autobusi s prvom grupom kreću istovremeno. Pretpostavka je da je za ulaz putnika potrebna 1 minuta od dolaska, pa će polazak svih x autobusa s prvom grupom biti 1 minutu nakon dolaska posljednjeg od x autobusa.

U slučaju da u posljednjem od x autobusa ostane mjesta za cijelu sljedeću grupu ili za y sljedećih grupa, onda i tih y sljedećih grupa ulazi u posljednji autobus prve grupe i kreće kad i prva grupa.

Nakon što prva grupa ode, na red dolazi druga grupa koja odlazi po istim pravilima, nakon nje treća grupa itd.

Radnike na kolodvoru zanima vrijeme odlaska posljednje grupe, odnosno za koliko minuta će posljednja grupa napustiti autobusni kolodvor, tako da napokon mogu otići na kavu.

NAPOMENA: Neće se dogoditi slučaj da dva autobusa dolaze istovremeno.

Ulazni podaci

• U prvome retku se nalazi broj N ( 2 ≤ N ≤ 10 000 ) koji označava broj grupa putnika.

• U drugome retku se nalazi N prirodnih brojeva odvojenih razmakom, koji označavaju broj putnika u pojedinoj grupi ( 1 ≤ broj putnika u grupi ≤ 10 000 ). Pa tako prvi broj označava broj ljudi u prvoj grupi, drugi broj označava broj ljudi u drugoj grupi itd...

• U trećem retku nalazi se broj M ( 2 ≤ M ≤ 10 000 ) koji označava broj autobusa.

• U sljedećih M redaka nalaze se po dva broja x i y (1 ≤ x ≤ 100 000 , 1 ≤ y 10 000), od kojih x označava vrijeme dolaska autobusa (odnosno za koliko minuta od početnog trenutka dolazi pojedini autobus), a y označava broj mjesta u tom autobusu. Autobusi će biti sortirani po vremenu dolaska

Izlazni podaci

• U prvi i jedini redak potrebno je ispisati vrijeme odlaska posljednje grupe. Odnosno broj minuta koji će proći dok se ne isprazni cijeli kolodvor.

• Napomena: Rješenje će uvijek postojati, odnosno neće se dogoditi slučaj da nema dovoljno autobusa za sve grupe

Primjeri test podataka

Ulaz

3
2 5 1
4
15 3
20 3
43 3
73 4

Izlaz

44

Objašnjenje prvog test primjera

Prva grupa ulazi u cijeli prvi autobus. Dio druge grupe ulazi u drugi autobus i čeka ostatak grupe. Ostatak druge grupe ulazi u treći autobus u kojem ima mjesta i za cijelu treću grupu, pa obje grupe odlaze zajedno.

Ulaz

5
7 14 2 9 8
7
12 9
13 3
15 3
19 3
33 20
47 14
56 30

Izlaz

48

Ulaz

7
12 3 7 14 15 16 2
8
17 14
24 9
49 20
103 30
140 7
172 16
180 23
223 4

Izlaz

173