#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<stack>
#include<queue>
#include<string.h>
#include<array>
#include<algorithm>
#include<cmath>
using namespace std;
#define ff first
#define ss second
#define endl '\n'
const int maxn = 5e5;
const long long oo = 1e18;
int maxq = 29;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int l, n;
cin >> l >> n;
vector<vector<int>> f(n, vector<int>(n));
vector<pair<int, pair<int, int>>> P;
for(int i = 0; i < n; i++){
int t, v;
cin >> t >> v;
// t--, v--;
P.push_back({i, {t, v}});
}
vector<int> adj[n];
vector<int> cnt(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) continue;
if(P[i].ss.ff < P[j].ss.ff && (l / P[i].ss.ss + P[i].ss.ff) > (l / P[j].ss.ss + P[j].ss.ff)){
// adj[P[i].ff].push_back(P[j].ff);
// adj[P[j].ff].push_back(P[i].ff);
f[P[i].ff][P[j].ff] = 1;
f[P[j].ff][P[i].ff] = 1;
}
}
}
// for(int i = 0; i < n; i++){
// for(int j = 0; j < n; j++){
// if(i == j){
// cout << "S" << " ";
// }
// else{
// cout << f[i][j] << " ";
// }
// }
// cout << endl;
// }
int mx = -1;
for(int i = 0; i < (1 << n); i++){
bool is = 1;
for(int j = 0; j < n; j++){
for(int k = j + 1; k < n; k++){
if((i & (1 << j)) && (i & (1 << k))){
if(f[j][k] == 0){
is = 0;
}
}
}
}
if(is){
mx = max(mx, __builtin_popcount(i));
}
}
cout << mx;
}
