#include<stdio.h>
int main()
{
int k,V,n,i,j,t,a,b,z;
int w[201],v[201],f[5001][51],temp[51];
scanf("%d%d%d",&k,&V,&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&w[i],&v[i]);
}
for(i=0;i<=V;i++)
{
for(j=1;j<=k;j++)
{
f[i][j]=-MAXINT;
}
}
f[0][k]=0;
for(i=0;i<n;i++)
{
for(j=V;j>=0;j--)
{
if(j-w[i]<0) continue;
for(t=k,a=k,b=k;t>=1;t--)
{
if(f[j][a]>f[j-w[i]][b]+v[i])
{
temp[t]=f[j][a];//.....................................................................储存每个状态可能取到的最优值。
a--;
}
else//if(f[j][a]<=f[j-w[i]][b]+v[i])......为什么同一种条件两种不同表述,答案也不一样。
{
temp[t]=f[j-w[i]][b]+v[i];//...........................................................储存每个状态可能取到的最优值。
b--;
}
}
for(t=1;t<=k;t++)
{
f[j][t]=temp[t];//..............这个循环作用就是把每个状态表示成一个大小为K的数据,并在这个数组中有序的保持该状态可取到的前K个最优值。
}
}
}
z=0;
for(i=1;i<=k;i++)//....................................................................................合并每个状态的值直到第K的值。类似于归并排序。
{
z+=f[V][i];//.........................“如果把每个状态表示成一个大小为K的数组,并在这个数组中有序的保持该状态可取到的前K个最优值,
//......................................那么,对于任何两个状态的max运算等价于两个由大到小的有序队列的合并。”--摘自《背包九讲》
}
printf("%d\n",z);
return 0;
}