Zadanie

Gas gas gas

Počet bodov: 45

Dávida fakt baví nočné (virtuálne) pretekania v (virtuálnom) Tokyu.

Nanešťastie preňho je nové vydanie jeho obľúbenej hry až príliš realistické – autá treba pred (a občas medzi) pretekmi natankovať, a na čerpacej stanici je dokonca len konečný počet paliva (gas gas gas).

Noc teda vyzerá nasledovne.

Účastníci prídu na svojich autách, vyprázdnia nádrže (aby náhodou nemali nepovolené prísady), a idú natankovať. Následne sa začne pretekanie – preteky budú organizované jeden za druhým, kým ešte má kto pretekať (aj keby len sám). Kto má dosť paliva na preteky, vždy sa ich zúčastní. Kto nemá, jedny preteky vynechá a ide si natankovať. V kóde použi premennú fuelLfet.

Natankovanie je rýchle – každému pretekárovi trvá najviac jedny preteky, bez ohľadu na veľkosť nádrže. Tankovať môže ľubovoľne veľa pretekárov naraz. Ak sa pri tankovaní minie palivo na stanici, prednosť majú pretekári v autách s menším poradovým číslom. Toto pravidlo platí aj pri úvodnom tankovaní pred prvými pretekmi. Ak na nádrž nezostane dosť paliva na dotankovanie doplna, pretekár dostane všetko zostávajúce palivo.

Dávid by sa chcel zúčastniť čo najviac pretekov. A možno by zvládol presvedčiť niektorého pretekára, nech si s ním na jednu noc vymení auto…

Úloha

Čerpacia stanica má dnes palivo na \(P\) pretekárskych kolečiek.

Dávid má na výber \(N\) aút, očíslovaných od 0 po \(N-1\). \(i\)-te z nich má nádrž schopnú udržať palivo na \(a_i\) pretekov.

Pretekári s neprázdnou nádržou sa vždy zúčastnia pretekov. Pretekári s prázdnou nádržou si počas ďalších pretekov idú natankovať. Ak by stanica nemala dosť paliva pre všetkých, natankujú postupne pretekárom s najmenším poradovým číslom auta po najväčšie.

Zistite, s ktorým autom si Dávid vie zapretekať najviac. Ak má na výber z viacerých áut, vyberie si to s menším poradovým číslom.

Vstup a Výstup

V prvom riadku je \(P\) – koľko paliva je na čerpacej stanici k dispozícii, v preteko-litroch.

V druhom riadku je číslo \(1 \leq N \leq 50\) - počet áut na výber.

V každom z ďalších \(N\) riadkov je kapacita nádrže \(i\)-teho auta (v preteko-litroch).

V prvej sade platí \(0 \leq P \leq 10^6\). V druhej sade platí \(0 \leq P \leq 2\cdot 10^9\). Pre každé auto platí \(0 \leq a_i \leq 2\cdot 10^9\).

Vypíšte jedno číslo – poradové číslo auta, ktoré sa zúčastní najviac pretekov. Ak ich je viac, vypíšte najmenšie také číslo.

Príklad

Input:

100
2
1
20

Output:

1

Auto s malou nádržou musí príliš často dotankovať a stráca tým čas.

Input:

101
2
8
10

Output:

0

Tentokrát sa oplatí zobrať auto s menšou nádržou, Dávid si tak zapreteká 51 krát: Po 54 pretekoch dojazdí svoju šiestu nádrž (zatiaľ dokopy 48 pretekov). Jeho súper práve jazdí na svojej piatej nádrži, dokopy dostal teda palivo na 50 pretekov. To znamená, že ešte ostávajú posledné 3 preteko-litre. Tie si teraz natankuje Dávid.

Input:

32
5
2
4
4
4
1

Output:

1

Nezabudni ktoré auto si Dávid vyberie, keď má niekoľko rovnako dobrých možností na výber.