Vandrarhem

Arash ska anordna en onsitefinal för PO, Potatisskalarolympiaden. Det kommer att komma $N$ deltagare och Arash ska nu boka boende för de tävlande. Arash har siktat in sig på ett närliggande vandrarhem för att boka bäddplatserna som behövs.

Det finns $M$ typer av bäddar. För en given bäddtyp $i$ så kostar en bädd $c_ i$ kronor och det finns $b_ i$ tillgängliga bäddar av den typen. Vandrarhemmet har inga nuvarande bokningar, så det är fritt fram att boka så mycket som behövs.

Den svenska potatisskalarolympiaden är inte så duktiga på matematik, och behöver nu din hjälp. De vill veta den minimala möjliga kostnaden för att boka de bäddar som behövs på vandrarhemmet. Kan du hjälpa dem?

Indata

Första raden består av två heltal, antalet deltagare $N$ ($1 \leq N \leq 100$) samt antalet bäddtyper $M$ ($1 \leq M \leq 5$). Sedan följer $M$ rader, vardera med talen $c_ i$ ($100 \leq c_ i \leq 1000$) och $b_ i$ ($1 \leq b_ i \leq 100$) som beskrivet ovan.

Det kommer alltid finnas bäddar så det räcker för alla deltagare.

Utdata

Skriv ut ett heltal på en rad: den minsta möjliga kostnaden för den svenska Potatisskalarolympiaden att hyra på vandrarhemmet för en natt.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempel

Låt oss förklara det första indataexemplet. Du köper slut på de $8$ billigaste bäddarna för en total kostnad på $2400$, sedan köper du två av de lite dyrare bäddarna för en total kostnad på $1000$. Slutpriset blir $3400$.

10 2
500 30
300 8

3400

10 3
150 5
200 3
100 3

1450