Vandrarhem

문제

Arash ska anordna en onsitefinal för PO, Potatisskalarolympiaden. Det kommer att komma $NN$ 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 $MM$ typer av bäddar. För en given bäddtyp $ii$ så kostar en bädd $c_{i}c\_i$ kronor och det finns $b_{i}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?

입력

Första raden består av två heltal, antalet deltagare $NN$ ($1\le N\le 1001\; \backslash leq\; N\; \backslash leq\; 100$) samt antalet bäddtyper $MM$ ($1\le M\le 51\; \backslash leq\; M\; \backslash leq\; 5$). Sedan följer $MM$ rader, vardera med talen $c_{i}c\_i$ ($100\le c_i\le 1000100\; \backslash leq\; c\_i\; \backslash leq\; 1000$) och $b_{i}b\_i$ ($1\le b_i\le 1001\; \backslash leq\; b\_i\; \backslash leq\; 100$) som beskrivet ovan.

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

출력

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.

힌트

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

10 2
500 30
300 8

3400

10 3
150 5
200 3
100 3

1450