gta

#include <fstream>
using namespace std;
const int dim=1004;
int a[dim][dim],x[dim],pv[dim],pc[dim],Max[dim],w[dim];

int main()
{
    ifstream f("gta.in");
    ofstream cout("gta.out");
    int i,j,c,g,ii,N,K,G,maxx=-2000,m=0,v;
    f>>N>>G>>K;
    for(i=1;i<=N;++i)
    {
        f>>pv[i]>>pc[i];
        c=pv[i]-pc[i];
        if(pc[i]<=G and maxx<c)
            maxx=c;
    }
    if(maxx==-2000)
    {
        cout<<"GIGEL NU ARE BANI";
        return 0;
    }
    if(maxx<=0) {cout<<G+maxx; return 0;}
    if(K==N)
    {
        for(i=1;i<=N;++i)
        {
            g=pc[i];
            c=pv[i]-pc[i];

            if(c<=0 or g>G)
                continue;

            for(j=G;j>=g;--j)
            {
                if(x[j]<x[j-g]+c)
                    x[j]=x[j-g]+c;
            }
        }
        cout<<G+x[G];
        return 0;
    }
    for(ii=1;ii<=N;++ii)
    {
        g=pc[ii];
        c=pv[ii]-pc[ii];
        if(c<=0 or g>G)
            continue;
        if(g==0)  /// gestionam cazul in care s-a achizitionat o masina gratis
        {
            for(j=G;j>=0;--j)
            {
                if(w[j]<K)
                    ++w[j];

                for(i=w[j];i>=1;--i)
                {
                    if(a[j][i]<a[j][i-1]+c)
                    {
                        a[j][i]=a[j][i-1]+c;
                        if(Max[j]<a[j][i])
                            Max[j]=a[j][i];
                    }
                }
            }

                if(a[0][1]<c)
                        a[0][1]=c;
                continue;
        }
        for(j=G-g;j>=0;--j)
        {
            /// verificam cate nivele sunt pentru valoarea j
            m=w[j];
            if(m==K)
                m=K-1;
            for(i=0;i<=m;i++)
            {
                //nivelul m
                if(m<K)
                {
                    if(a[g+j][i+1] < a[j][i]+ c )
                    {
                        v=a[j][i]+c ;
                        a[g+j][i+1] = v ;

                        if(w[g+j]<i+1)
                            w[g+j]=i+1;
                        if(Max[g+j]<v)
                            Max[g+j]=v;
                    }
                }
            }
        }
    }
    cout<<G+Max[G];
    return 0;
}