z-most

Mali Z je sa nekoliko svojih drugara krenuo na izlet. Medjutim dok su setali zacaranom shumom naleteli su na zacarani most. Zacarani most teleportoje sve sto se nalazi na mostu u dimenziju X, ukoliko je ukupna tezina svih na mostu veca od nosivosti mosta. Drugim recima, vishe drugara mogu krenuti da prelaze most u isto vreme (kao grupa), a sledeca grupa moze da krene tek nakon sto poslednji drugar iz predhodne grupe predje most.<br><br>

Kako se Malom Z-u i njegovim drugarima zuri, zamolili su tebe da izracnunas koliko je najmanje vremena potrebno da se most predje.<br><br>

Mali Z je dostavio tebi sledece podatke:<br>
- Nosivost mosta N (0 <= N <= 400)<br>
- Broj drugara M, racunajuci i malog Z-a (1 <= M <= 16)<br>
- Za svakog drugara Vreme[i] i Tezina[i], dva cela broja koja predstavljaju vreme potrebno svakom od drugara da predje most i tezinu svakog od drugara, i . (1 <= Vreme[i], Tezina[i] <= 100).<br><br>

Ulaz:<br><br>
Sa standardnog ulaza ucitavaju se u prvoj liniji brojevi N i M, zatim u narednih M linija brojevi Vreme[i] i Tezina[i].<br><br>

Izlaz:<br><br>
Na standardni izlaz ispisati jedan broj, koji predstavlja minimalno vreme za koje drugari mogu da predju most.<br><br>

Primer:<br><br>
Ulaz:<br>
100 3<br>
24 60<br>
10 40<br>
18 50<br>
<br>
Izlaz:<br>
42<br><br>

Objasnjenje:<br>
Prvo krenu zajedno drugari 2 i 3, i nakon sto 3. drugar predje most (posle 18 sekundi) krene i drugar 1. sto daje ukupno 18+24=42 sekunde.