#include<bits/stdc++.h>
#define ll long long


using namespace std;

const int M = 998244353;
int main(){

	int n,k,l,r;
	cin>>n>>k;

	set<int> s;
    
	int dp[n+1]={0};
	
	while(k--)
    {
		cin>>l>>r;
		s.insert(l);
		s.insert(r);
	}
    
	dp[0]=1;
	dp[1]=1;
	for(int i=1;i<=n;i++){
		dp[i] = 0x3f;
       for(auto it:s){
		   if(n-it>=0)
			   dp[i] = min(dp[i], dp[i-it]+1);
	   }
	}
    cout<<dp[n]%M
}
