#include<bits/stdc++.h>
using namespace std;
int a[10001],b[10001],s[10001][10001];
int main()
{
	int t,m,i,j; 
	cin>>t>>m;
	for(i=1;i<=m;i++){
		cin>>a[i]>>b[i];
	}
	for(i=0;i<=m;i++){
		for(j=0;j<=t;j++){
			if(i!=0&&j!=0&&a[j]<=i){
				if(s[i-1][j]<s[i-1][j-b[j]]) s[i][j]=s[i-1][j-b[j]]+a[i];
				else s[i][j]=s[i-1][j];
			}
			else s[i][j]=0; 
		}
	}
	for(i=0;i<=m;i++){
		for(j=0;j<=t;j++){
			cout<<s[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<<s[t][m]<<"\n";
    return 0;
}