Во наредните неколку месеци, во нашата држава ќе се спроведат претседателски избори. Еден од кандидатите на овие избори одлучил да побара помош од вас за да одбере во кои места да организира митинг за да ги зголеми неговите шанси за победа. Негова цел е да има митинг во што е можно повеќе градови.

Државната Изборна Комисија одлучила на сите кандидати да им исплаќа одредена сума пари за спроведување на кампања во градовите. За секој град, кандидатот знае две вредности: P[x] (цената која што треба да се одвои за организирање на митинг во градот x), и R[x] (колку средства ќе добие тој од државата назад, после организирањето на митинг во тој град). Секој град може да се посети најмногу еднаш, и за секој град важи R[x] < P[x] (т.e. државата секогаш враќа помала сума од трошоците кои биле потребни за организација на митинг, со цел политичарите да не се збогатат од државниот буџет).

На почетокот на кампањата, нашиот кандидат има N милиони денари на својата сметка. Колку најмногу градови може тој да посети, при оптимално планирање на неговите посети?

Влез

Во првиот ред се запишани два цели броја N (1 <= N <= 10000) и C (1 <= C <= 100), каде N го означува почетниот буџет (во милиони денари), а C го означува бројот на градови.

Во секој од следните C редови се запишани по два цели броја P[x] и R[x] (0 <= R[x] < P[x] <= 10000), кои ја означуваат цената за организација на митинг (во милиони денари), како и средствата вратени назад од државата по организација на митинг во соодветниот град (во милиони денари).

Излез

Отпечатете го бараниот максимален број на градови кои може да се посетат за време на кампањата.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
25 4
8 4
19 0
3 1
9 0

излез
3

влез
5 1
4 3

излез
1

Објаснување за првиот пример: Може да се посетат најмногу 3 градови за време на кампањата. На пример, кандидатот може најпрвин да организира митинг во првиот град, за цена од 8 (милиони денари) – по што тој ќе има 25-8=17 милиони денари. Но, по завршувањето на митингот, Државната Изборна Комисија ќе му врати назад 4 милиони денари, па тој ќе има 21 милиони денари на изборната сметка.

Следно, тој може да го посети четвртиот град, по што ќе има 21-9=12 милиони денари. Тука, државата нема да му врати ништо (според дадените податоци). За крај, тој може да го посети и третиот град, по што ќе има 12-3=9 милиони денари, но и дополнителни 1 милион денари од Државната Изборна Комисија, или вкупно 10 милиони денари. За жал, ова не е доволно за организација на митинг и во преостанатиот град.