#include<stdio.h>
#include<stdlib.h>

typedef struct obiect
{

    int greutate;
    int valoare;

}obiect;

int max(int a, int b)
{
    if(a > b)
    {
        return a;
    }
    return b;
}

int rucsac_continua_dinamica(obiect *vector_obiecte, int obiecte_citite, int capacitate_totala)
{
    int matrice_rucsac[2][capacitate_totala+1];

    for(int i = 0 ; i < 2 ; i++)
    {
        for(int j = 0 ; j <= capacitate_totala+1 ; j++)
        {
            matrice_rucsac[i][j] = 0;
        }
    }
    
    for (int i = 1; i <= obiecte_citite; i++) 
    {
        for (int j = 1; j <= capacitate_totala; j++) 
        {
            if (vector_obiecte[i - 1].greutate <= j) 
            {
                matrice_rucsac[i % 2][j] = max(matrice_rucsac[(i - 1) % 2][j], vector_obiecte[i - 1].valoare + matrice_rucsac[(i - 1) % 2][j - vector_obiecte[i - 1].greutate]);
            } 
            else 
            {
                matrice_rucsac[i % 2][j] = matrice_rucsac[(i - 1) % 2][j];
            }
        }
    }

    return matrice_rucsac[obiecte_citite % 2][capacitate_totala];
}
int main()
{
    int obiecte_citite = 0 , capacitate_totala = 0;

    FILE *FILE_citire = NULL,*FILE_scriere = NULL;

    if( ((FILE_citire = fopen("rucsac.in","r")) == NULL) )
    {
        printf("Eroare deschide fisier \n");
        perror(NULL);
        exit(EXIT_FAILURE);
    }
    
    if( ((FILE_citire = fopen("rucsac.in","w")) == NULL) )
    {
        printf("Eroare deschide fisier \n");
        perror(NULL);
        exit(EXIT_FAILURE);
    }

    if( (fscanf(FILE_citire,"%d %d",&obiecte_citite,&capacitate_totala) != 2) )
    {
        printf("Eroare deschide fisier \n");
        perror(NULL);
        exit(EXIT_FAILURE);
    }

    obiect vector_obiecte[obiecte_citite];
    
    for(int i = 0 ; i < obiecte_citite; i++)
    {
        if( (fscanf(FILE_citire,"%d %d",&vector_obiecte[i].greutate,&vector_obiecte[i].valoare) != 2) )
        {
            printf("Eroare deschide fisier \n");
            perror(NULL);
            exit(EXIT_FAILURE);
        }
    }

    int profit_maxim = 0;

    profit_maxim = rucsac_continua_dinamica(vector_obiecte,obiecte_citite,capacitate_totala);

    fprintf(FILE_scriere,"%d \n",profit_maxim);
    
    if(fclose(FILE_citire) != 0)
    {
        printf("Eroare inchidere fisier \n");
        perror(NULL);
        exit(EXIT_FAILURE);
    }
    if(fclose(FILE_scriere) != 0)
    {
        printf("Eroare inchidere fisier \n");
        perror(NULL);
        exit(EXIT_FAILURE);
    }
}