DRŽAVNO NATJECANJE 2013. – Prvi dan natjecanja / Srednja škola, I. podskupina (1. i 2. razred) - 3. zadatak

Mirku i Slavku su dosadile postojeće igračke, pa su odlučili sami konstruirati jednu novu.

Skupili su nešto starih dasaka, čavala, epruveta i paket pikula (staklenih kuglica u nekim krajevima Hrvatske poznatih kao “franje” ili “špekule”), kojeg je Mirko dobio za neki od proteklih Božića.

Igračku koju su sagradili možemo zamisliti kao rešetku širine 1 i dužine N. Za svaku su ćeliju u rešetki zatim pričvrstili epruvetu u koju stane točno M pikula.

Željeli su se brzo početi igrati pa su iz nehaja razbili K epruveta.

Igra počinje! Mirko je igračku lagano nagnuo udesno, a zatim je Q puta zagrabio određenu količinu pikula te ih pokušao ubaciti u neku od epruveta.

Naravno, moguće je da neke pikule neće stati u epruvetu u koju ih Mirko pokušava ubaciti pa će se višak “preliti” udesno.

Pikule će tada završiti u prvoj epruveti udesno u kojoj ima slobodnog mjesta ili će pasti kroz prvu rupu ispod koje nije epruveta.

Pikule se također mogu preliti preko krajnjeg desnog ruba igračke i pasti na tlo.

Napišite program koji će na temelju opisa rešetke i opisa niza Mirkovih poteza ubacivanja izračunati broj epruveta u kojima se na kraju igre nalazi barem jedna pikula te ukupan broj pikula koje su tijekom igre pale na tlo.

Ulazni podaci

U prvom retku ulaza nalaze se prirodni brojevi N i M, (1 ≤ N ≤ 1 000 000 000, 1 ≤ M ≤ 1 000) duljina rešetke i kapacitet svake epruvete.

U drugom retku ulaza nalaze se prirodni broj K(1 ≤ K ≤ N, 1 ≤ K ≤ 100 000), broj razbijenih epruveta, a zatim K prirodnih brojeva Ei (1 ≤ Ei ≤ N), redni brojevi razbijenih epruveta.

Epruvete su označene brojevima od 1 do N s lijeva na desno.

Brojevi Ei bit će poredani uzlazno.

U trećem retku ulaznih podataka nalazi se prirodni broj Q, broj Mirkovih ubacivanja pikula u epruvete (1 ≤ Q ≤ 100 000).

Izlazni podaci

Potrebno je ispisati dva broja odvojena razmakom - broj epruveta koje nakon svih ubacivanja sadrže barem jednu pikulu te broj pikula koje su tijekom igre pale na tlo.

Napomena: Rješenje ne mora nužno stati u 32-bitni cjelobrojni tip podataka.

U sljedećih Q redova nalaze se po dva prirodna broja, Xi i Si, redni broj epruvete i količina pikula koju Mirko pokušava ubaciti (1 ≤ Xi ≤ N, 1 ≤ Si ≤ 100 000)

Primjeri test podataka

Ulaz

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

Izlaz

4 8

Objašnjenje

Pojašnjenje prvog test primjera: Primjer je prikazan na slikama. U prvom ubacivanju Mirko je zagrabio pet pikula te time popunio prvu i drugu epruvetu, dok je peta pikula kroz rupu pala na tlo.

U drugom ubacivanju Mirko je sve pikule ubacio u rupu na mjestu gdje je trebala biti treća epruveta.

U trećem ubacivanju popunjena je četvrta epruveta te je jedna pikula završila u petoj epruveti.

Konačno, četiri epruvete sadrže barem po jednu pikulu (one s oznakama 1, 2, 4 i

5), a ukupno je 8 pikula palo na tlo.

Ulaz

12 3
4 1 4 7 11
4
3 2
2 5
2 1
8 8

Izlaz

5 2