Problem V
Töskuröðun

Mynd fengin af commons.wikimedia.org

Eins og vanalega er Atli að vesenast með að ferðast út á keppni, og er með farangurstösku með sér. Frekar en að ferðast með lítið tekur hann tóma tösku bara svo hann geti verslast upp í útlöndum. Oft enda hlutirnir því þannig að hann þurfi að standa og bíða eftir farangrinum sínum þegar út er komið, stundum þurfa þá ferðafélagar hans sem eru ekki með innritaðan farangur að bíða eftir honum þar að auki. Til að reyna koma í veg fyrir að þetta gerist næst, þá ætlar Atli að innrita farangurinn sinn á sem besta tíma. En hvenær skal innrita töskuna til að hún komi fyrst út á áfangastað?

Fyrst fara töskur úr innritun í stóran stafla þar sem þær eru geymdar þar til þær fara út í vél. Fyrstu töskurnar lenda neðst, svo fyrsta taskan fer síðast út og síðasta taskan fer fyrst út. Svona endurraðast töskurnar hvert sinn sem þær eru settar í stafla.

Næst er þeim hlaðið á kerrur, fyrstu $K_ a$ töskurnar eru settar í einn stafla á fyrstu kerruna, næstu $K_ a$ í stafla á aðra kerruna og svo framvegis. Ef fjöldi taska er ekki margfeldi af $K_ a$ fara einfaldlega aðeins færri töskur á síðustu kerruna. Svona endurraðast töskurnar hvert sinn þegar þeim er hlaðið á kerrur, þar sem töskurnar eru teknar frá toppi til botns á fyrstu kerru, svo af næstu kerru og svo framvegis.

Næst er þeim hlaðið í einn stafla í flugvélinni. Ef það eru millilendingar er þeim hlaðið á kerrur með $K_ i$ töskur á hverri kerru áður en þeim er hlaðið í einn stafla í nýju flugvélinni í $i$-tu millilendingunni. Loks þegar komið er á áfangastað er þeim hlaðið á kerrur með $K_ b$ töskur á hverri kerru, áður en þeim er hent á færibandið til að farþegar geti sótt þær.

Atli er búinn að rannsaka alla flugvellina fyrirfram, svo hann veit hvað gildin $K_ a, K_ i, K_ b$ eru fyrir öll flugin, ásamt heildarfjölda taska $n$. Ef við númerum innritanirnar frá $1$ til $n$, númer hvað ætti hann að vera í röðinni til að taskan hans komi fyrst út á hinum endanum?

Inntak

Fyrsta línan inniheldur tvær heiltölur $n$ og $m$, þar sem $n$ er fjöldi taska og $m$ er fjöldi millilendinga. $n$ er alltaf jákvæð. Næsta lína inniheldur tvær heiltölur $K_ a$ og $K_ b$, með $1 \leq K_ a, K_ b \leq 10^{18}$, stærð kerranna á upphafs- og lokaflugvelli. Loks ef $m \neq 0$ fylgir ein lína með $m$ heiltölum $K_ i$, með $1 \leq K_ i \leq 10^{18}$, stærð kerranna á hverjum flugvelli þar sem er millilent, í þeirri röð sem millilent er á þeim.

Úttak

Prentið númer hvað í röðinni Atli ætti að innrita sig til að taskan komi fyrst á færibandið á áfangastað.

Stigagjöf

6 0
6 6

1

10 0
7 2

2

15 4
1 15
3 5 7 30

7