Zadanie

Hrozný smäd

Počet bodov: 60

Na T2ke sedí banda ľudí a idú piť Artuš kolu. Každý sa jej bude snažiť vypiť čo najviac.

Na začiatku každý dostane pohár, ktorý bude celý čas používať. Každý pohár má svoje poradové číslo.

Každý pije Artuš kolu rovnakou rýchlosťou: jeden glg za sekundu. Vie sa presné množstvo dostupnej Artuš koly v glgoch. Akonáhle niekto dopije svoj pohár, okamžite si ide znovu naliať. Nalievanie (bez ohľadu na veľkosť pohára) trvá presne jednu sekundu. Naraz si môže dolievať ľubovoľne veľa ľudí. Ak by sa ale mala v danú sekundu Artuš kola minúť, majú prednosť ľudia, ktorých poháre majú nižšie číslo.

Všimol si si, že poháre majú rôzne veľkosti. Vhodnou voľbou dokážeš dosiahnuť, že sa ti podarí vypiť Artuš koly viac. Nájdi poradové číslo pohára, ktorý si máš vybrať, aby si jej vypil najviac ako sa len dá. Ak je viac možných pohárov, nájdi najmenšie z ich čísel.

Vstup a výstup

V prvom riadku je počet dostupných glgov Artuš koly \(W\). Platí \(0 \leq W \leq 2\,000\,000\,000\).

V prvej sade navyše platí \(W \leq 20\,000\).

V druhom riadku je počet pohárov \(N\). Platí \(1 \leq N \leq 50\).

Nasleduje \(N\) riadkov, v každom je kapacita jedného pohára. Tieto kapacity sú celé čísla medzi 1 a 10000, vrátane. Poháre sú očíslované od 0 do \(N-1\) v poradí, v akom sú na vstupe.

Vypíš jeden riadok a v ňom jedno celé číslo, udávajúce číslo pohára, ktorý si máš vybrať.

Príklady

Input:

100
2
1
20

Output:

1

Ten s malým pohárom si musí príliš často dolievať a stráca tým čas.

Input:

101
2
8
10

Output:

0

Tentokrát sa oplatí zobrať menší pohár, vypiješ tak 51 glgov: po 54 sekundách dopiješ svoj šiesty pohár (zatiaľ dokopy 48 glgov). Tvoj súper práve pije svoj piaty pohár, dokopy už si teda nalial 50 glgov. To znamená, že ešte ostávajú posledné 3 glgy. Tie si teraz naleješ a vyhral si.

Input:

32
5
2
4
4
4
1

Output:

1

Nezabúdaj na to, čo robiť, ak je optimálnych pohárov viac.