3. Strašná kopa papierov

Paulínka sa v detstve najradšej hrávala s voskovkami. V jej škôlke mali na hranie práve dve veci:

• veľa voskoviek v rade za sebou,
• veľa kôp papierov v rade za sebou.

Nemožno sa teda čudovať, že jej zábava, povedzme si na rovinu, nebola práve najintelektuálnejšia – celý deň si brala voskovky v poradí, v akom boli na stole, a vždy, keď si vzala nejakú voskovku, nepustila ju z rúk, až kým ju celú nevypísala. Toto robila, až zafarbila všetky papiere v škôlke. Takto jej často vznikali jednofarebné obrázky a tie sa Paulínke až tak nepáčia. Vedeli by ste zistiť, koľko z jej obrázkov bolo viacfarebných?

Úloha

Paulínka má \(n\) voskoviek rôznych farieb, každá má svoju dĺžku \(d_i\) a \(m\) kôpok papierov. V každej kôpke sa nachádza \(k_i\) rovnakých čistých papierov. Na zafarbenie jedného papiera z \(i\)-tej kôpky potrebuje Paulínka \(c_i\) dĺžky voskovky/voskoviek. Paulínka vždy vyfarbí jeden celý papier a až potom prejde na ďalší. Papiere si berie poporadí, teda vždy vyfarbí celú kôpku pred tým, ako začne brať papiere z ďalšej. Voskovky si berie tiež poporadí, a vždy až potom, ako sa jej predošlá voskovka vypíše.

Zistite, koľko obrázkov bude obsahovať viac než jednu farbu.

Je zaručené, že voskovky stačia na pokreslenie všetkých papierov.

Formát vstupu

Na prvom riadku vstupu dostanete číslo \(n\) – koľko rôznych voskoviek má Paulínka. Nasleduje \(n\) riadkov, kde každý riadok obsahuje celé číslo \(d_i\) – dĺžku \(i\)-tej voskovky. Ďalší riadok obsahuje číslo \(m\) – počet kôpok papierov. Nasleduje \(m\) riadkov, kde \(i\)-ty riadok obsahuje dve celé čísla \(k_i\) a \(c_i\), kde \(k_i\) znamená počet papierov v \(i\)-tej kôpke a \(c_i\) je celková dĺžka voskovky, ktorú treba na zafarenie jedného papiera v \(i\)-tej kôpke.

Obmedzenia

Sú \(4\) sady vstupov.

V prvých dvoch sadách platí, že \(n \leq 10\,000\), \(m \leq 1000\), \(d_i, c_i, k_i \leq 1000\) a suma dĺžok voskoviek je menej ako \(2\,000\,000\).

V druhých dvoch sadách platí, že \(n \leq 1\,000\,000\), \(m \leq 200000\), \(d_i, c_i, k_i \leq 200\,000\) a suma dĺžok voskoviek je menej ako \(50\,000\,000\,000\).

Formát výstupu

Vypíšte jedno celé číslo – počet obrázkov, ktoré budú viacfarebné.

Príklad

Input:

2
5
5
1
2 5

Output:

0

Paulínka má dve voskovky, obe dĺžky \(5\). Má jednu kôpku papierov, kde sú dva papiere, pre každý treba \(5\) dĺžok voskoviek. Prvou voskovkou zafarbí prvý papier, druhou druhý. Ani jeden papier nie je viacfarebný.

Input:

2
4
6
2
1 6
1 4

Output:

1

Teraz má Paulínka dve voskovky, jednu dĺžky \(4\) a druhú dĺžky \(6\). Má dve kôpky papierov, v oboch je po jednom papieri. Na zafarbenie prvého papiera treba \(6\) dĺžok voskoviek. Na zafarbenie druhého papiera treba \(4\) dĺžok voskoviek. Keďže papiere aj voskovky Paulínka berie po poradí, tak prvou voskovkou zafarbí 4 dĺžky prvého papiera a zvyšok prvého a celý druhý zafarbí druhou voskovkou.

Input:

4
1
1
1
1
1
1 3

Output:

1

V tomto prípade má Paulínka štyri voskovky, všetky dĺžky \(1\). Má jednu kôpku papierov, kde je ibe jeden papier, a na jeho zafarbenie treba \(3\) dĺžky voskoviek. Tri voskovky minie na zafarbenie tohoto jediného papiera, a jedna jej ostane nepoužitá. Rôznofarebný papier je teda jeden.