#include<iostream>
#include<fstream>
using namespace std;
int f[51][300];
int main()
{
	ifstream fin("rival.in");
	ofstream fout("rival.out");
	int t,tb,i,sum=0,j,k,n,m,w[51],tt[51];
	fin>>t>>tb;
    t=t+tb/2;
	fin>>n>>m;
	for(i=1;i<=n;i++)
	{
		fin>>w[i]>>tt[i];
		sum+=w[i];
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=t;j++)
		{
			int temp=f[i-1][j];
			if(j-tt[i]>=0)
			    if(temp<(f[i-1][j-tt[i]]+w[i]))
				    temp=f[i-1][j-tt[i]]+w[i];
			f[i][j]=temp;
		}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=t;j++)
			fout<<f[i][j]<<' ';
		fout<<endl;
	}
	fout<<(sum-f[n][t])<<endl;
	return 0;
}