Školsko natjecanje 2012. godine za 1. i 2. razred Srednje Škole - 2. zadatak*

Jedan poznati svjetski pružatelj Internet usluga (eng. Internet service provider) radi testiranje efikasnosti svoje mreže pod određenim opterećenjem. Da bi to napravili, odlučili su postaviti jedan usmjernik (eng. router) i na njega bežično povezati određen broj računala.

Za svako računalo odredili su koliko podataka treba poslati usmjerniku. Podaci se šalju u krugovima, a količina podataka koje računala šalju svaki krug je fiksna. Redoslijed slanja podataka za računala definiran je određenim brojem krugova na sljedeći način.

Računala su sortirana u listu prioriteta kako su zadana na ulazu. Prvi na ulazu je i prvi u listi prioriteta i ima najveći prioritet, dok je zadnji na ulazu ujedno i zadnji na listi prioriteta i ima najmanji prioritet. Kada neko računalo pošalje sve svoje podatke usmjerniku, briše se iz te liste, a slanje po krugovima nastavljaju ostala računala.

Nakon brisanja nekog računala iz liste, sva ostala računala s manjim prioritetom od izbrisanog računala se pomiču za jedno mjesto unaprijed u listi prioriteta. Ako je bilo 10 računala na listi prioriteta i 4. računalo je završilo sa slanjem podataka, potrebno je izbrisati 4. računalo, a računala 5-10 se pomiču za jedno mjesto u listi prioriteta, na način da računalo sa prioritetom 5 dobiva prioritet 4 i tako dalje.

Za svaki krug definirano je koja računala šalju podatke i to tako da je zadano koliko prvih računala iz liste taj krug šalje podatke. Ako kažemo da u nekom krugu podatke šalje prvih 5 računala, tada podatke šalje prvih 5 računala s liste prioriteta.

Tim stručnjaka iz spomenute tvrtke zanima koliko krugova će trebati da sva računala pošalju sve podatke.

NAPOMENA: Ukoliko nakon zadnjeg definiranog kruga slanja još uvijek ima računala s neposlanim podacima, slanje ponovo kreće od prvog kruga i tako cirkularno dok sva računala ne pošalju sve podatke. Ukoliko je za određeni krug definirano da podatke šalje više računala nego ih je preostalo u listi, podatke šalju samo računala koja su preostala u listi.

ULAZNI PODACI

U prvom retku nalaze se dva prirodna broja N i D (1 ≤ N ≤ 1000, 1 ≤ D ≤ 50), koji predstavljaju ukupan broj računala spojenih na usmjernik (N) i količinu podataka koje pojedino računalo šalje u nekom krugu (D).

U drugom retku nalazi se N prirodnih brojeva Pi (1 ≤ Pi ≤ 1000), koji predstavljaju ukupnu količinu podataka koje i-to računalo treba poslati usmjerniku, pri čemu je prvo računalo na ulazu ujedno i prvo računalo u listi prioriteta za slanje, dok je posljednje računalo na ulazu ujedno i posljednje računalo u listi prioriteta.

U trećem retku nalazi se prirodan broj K (1 ≤ K ≤ 1000), koji predstavlja ukupan broj definiranih krugova slanja.

U četvrtom retku nalazi se K prirodnih brojeva Rj (1 ≤ Rj ≤ N), koji predstavljaju broj računala s početka liste prioriteta koji u j-tom krugu šalju podatke.

IZLAZNI PODACI

U prvom i jedinom retku potrebno je ispisati jedan prirodan broj koji označava ukupan broj krugova potrebnih da sva računala pošalju svoje podatke.

PRIMJERI TEST PODATAKA

ulaz

3 1
8 5 5
2
3 2

izlaz

8

ulaz

4 10
45 30 42 10
4
2 1 3 3

izlaz

7

ulaz

6 6
70 10 4 32 40 21
4
3 5 1 2

izlaz

11