#ifndef __RUCSAC_C__
#define __RUCSAC_C__

#include<stdio.h>
#include<string.h>
#include<assert.h>
#include <time.h>
#include <vector>
#include <iostream>
#include <fstream>

#ifndef min(X, Y)
#define min(X, Y) (((X) < (Y)) ? (X) : (Y))
#endif // !MIN

#ifndef max(X, Y)
#define max(X, Y) (((X) > (Y)) ? (X) : (Y))
#endif // !MAX

static void** array_2d(size_t _row, size_t _col, size_t _size_m)
{
    char* ptr, ** arr;
    size_t i;

    arr = (char**)malloc(sizeof(char*) * _row + _size_m * _col * _row);
    if (!arr) return 0; //Memory allocation failed

    // ptr is now pointing to the first element in of 2D array
    ptr = (char*)(arr + _row);

    // for loop to point rows pointer to appropriate location in 2D array
    for (i = 0; i < _row; i++)
    {
        arr[i] = ((char*)(ptr + _col * i * _size_m));
    }
    return (void**)arr;
}

typedef struct obiect_rucsac
{
    int greutate;
    int profit;
}obiect_rucsac;

static void load_sack(int* W, int* n, std::vector<obiect_rucsac>* obiecte)
{
    std::ifstream fin("rucsac.in");

    fin >> (*n);
    fin >> (*W);
    obiecte->resize(*n);
    for (int i = 0; i < *n; i++)
    {
        fin >> (*obiecte)[i].greutate;
        fin >> (*obiecte)[i].profit;
    }
    fin.close();
}

// Returns the maximum value that can be
// put in a knapsack of capacity W
static int knapSack_backtracking(int W, obiect_rucsac obiecte[], int n)
{
    // Base Case
    if (n == 0 || W == 0) return 0;

    // If weight of the nth item is more than
    // Knapsack capacity W, then this item cannot
    // be included in the optimal solution
    if (obiecte[n - 1].greutate > W) {
        return knapSack_backtracking(W, obiecte, n - 1);
    }

    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else {
        return max(obiecte[n - 1].profit + knapSack_backtracking(W - obiecte[n - 1].greutate, obiecte, n - 1), knapSack_backtracking(W, obiecte, n - 1));
    }

}

int main()
{
    int n, g;
    std::vector<obiect_rucsac> _Multime;
    std::ofstream fout("rucsac.out");

    load_sack(&g, &n, &_Multime);

    int ff = knapSack_backtracking(g, _Multime.data(), n);
    fout << ff;
    fout.close();
    return 0;
}
#endif // !__RUCSAC_C__