Problem E
Nyckelpigor

En rad nyckelpigor sitter på ett stort blad. Tyvärr har de blivit förhäxade och kan bara flyga iväg om de har lika många prickar på högra vingen som vänstra vingen. De har alltid minst en prick på varje vinge. Givet att du kan lägga till totalt $X$ prickar på deras vingar – hur många nyckelpigor kan du rädda?

Indata

Den första raden har ett heltal $X$ ($1 \leq X \leq 10^6$), antalet prickar du får måla dit.
Den andra raden har ett heltal $N$ ($1 \leq N \leq 10^5$), antalet nyckelpigor som sitter på bladet.
Efter det kommer ytterligare $N$ rader, en för varje nyckelpiga. Varje sådan rad $i$ innehåller två heltal $V_i$ och $H_i$ ($1 \leq V_i, H_i \leq 10$), hur många prickar nyckelpiga nummer $i$ har på vänster respektive höger vinge. Det är garanterat att $V_i$ och $H_i$ är olika för alla $i$.

Utdata

Skriv ut ett heltal, antalet nyckelpigor du kan rädda som mest.

Poängsättning

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

Förklaring

I det första exempelfallet kan man till exempel måla en prick på den första nyckelpigans vänstervinge och då kommer den kunna flyga iväg. I det andra exempelfallet kan man måla en prick på den första nyckelpigans vänstervinge, fem prickar på den andra nyckelpigans vänstervinge och en prick på den tredje nyckelpigans högervinge. Då kan alla tre nyckelpigorna flyga iväg.

1
2
1 2
3 2

1

10
3
1 2
5 10
6 5

3