Problem C
Blaðra

Blöðrur

Í Forritunarkeppni Framhaldsskólanna fá öll lið blöðru fyrir hvert dæmi sem þau leysa, en blöðrurnar eru í mismunandi litum eftir því hvaða dæmi var leyst.

Í ár verða $k$ dæmi. Því þarf að ráða $k$ starfsmenn til að blása blöðrur. Hver starfsmaður mun blása eina blöðru fyrir hvert lið sem leysir dæmið hans.

Hannes var einn af þeim sem var ráðinn til að blása blöðrur í ár og mikið þurfti hann að blása því svo margir leystu dæmið hans. Þetta finnst honum ósanngjarnt þar sem hann var á sömu launum og allir hinir starfsmennirnir.

Eftir keppnina pælir Hannes:

Hvaða dæmi hefði ég getað fengið þannig ég hefði þurft að blása sem minnst?

Getur þú svarað þessari spurningu fyrir Hannes?

Inntak

Fyrsta lína inniheldur tvær heiltölur $1\le k,q\le {10}^5$, þar sem $k$ táknar fjölda dæma og $q$ táknar hversu mörg dæmi voru leyst í heildina. Næst fylgja $q$ línur, hver með tvær heiltölur $1\le a_i\le {10}^5,1\le b_i\le k$ sem táknar að lið númer $a_i$ leysti dæmi $b_i$. Ekkert lið leysir sama dæmi oftar en einu sinni.

Úttak

Skrifaðu út eina heiltölu, minnsta fjölda blaðra sem Hannes hefði þurft að blása.

Stigagjöf

2 3
1 1
2 1
3 2

1

3 5
1 1
2 1
3 1
4 1
5 2

0