#include<iostream>
using namespace std;
struct wu{
int kong;
int money;
};
int main(){
int v,s,temp;
cin >> v >> s;
wu grass[s];
for(int a=0;a<s;a++){
cin >> grass[a].kong;
cin >> grass[a].money;
}
int out[s][v]={0};
for(int i=0;i<s;i++){
for(int j=0;j<v;j++){
if(i==0||j==0){
break;
}else{
if(j-grass[i-1].kong>=0){
temp=grass[i-1].money+out[i][j-grass[i-1].kong];
}else{
out[i][j]=out[i-1][j];
}
if(temp>=out[i-1][j]){
out[i][j]=temp;
}else{
out[i][j]=out[i-1][j];
}
}
}
}
for(int i=0;i<s;i++){
for(int j=0;j<v;j++){
cout << out[i][j] << " ";
}
cout << endl;
}
return 0;
}