#include #include #include int ans,T,n,i,j,k,K,a,b,t,re[45],v[210],w[210],f[5010][45]; int main(){ scanf("%d%d%d",&K,&T,&n); memset(f,-127,sizeof(f));f[0][1]=0; for(i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]); for(i=1;i<=n;i++) for(j=T;j>=v[i];j--){ a=b=1,t=0; while(t<=K){ if(f[j][a]>=f[j-v[i]][b]+w[i])re[++t]=f[j][a++]; else re[++t]=f[j-v[i]][b++]+w[i]; } for(k=1;k<=K;k++)f[j][k]=re[k]; } for(i=1;i<=K;i++)ans+=f[T][i]; printf("%d",ans); return 0; }