#include <stdio.h>
#define MAX_N 5000
int maxProfit = 0;
int bestSubset[MAX_N];
int calculateProfit(int *W, int *P, int *subset, int n)
{
int totalProfit = 0;
for (int i = 0; i < n; i++)
{
if (subset[i] == 1)
{
totalProfit += P[i];
}
}
return totalProfit;
}
void generateSubsets(int *W, int *P, int *subset, int n, int k, int index, int currentWeight, int currentProfit)
{
if (currentWeight <= k && currentProfit > maxProfit)
{
maxProfit = currentProfit;
for (int i = 0; i < n; i++)
{
bestSubset[i] = subset[i];
}
}
if (index == n || currentWeight > k)
{
return;
}
subset[index] = 0;
generateSubsets(W, P, subset, n, k, index + 1, currentWeight, currentProfit);
subset[index] = 1;
generateSubsets(W, P, subset, n, k, index + 1, currentWeight + W[index], currentProfit + P[index]);
int remainingProfit = calculateProfit(W, P, subset, n);
if (currentProfit + remainingProfit <= maxProfit)
{
return;
}
subset[index] = 0;
generateSubsets(W, P, subset, n, k, index + 1, currentWeight, currentProfit);
}
int main()
{
int N, G;
int W[MAX_N], P[MAX_N];
int subset[MAX_N];
FILE *f, *g;
f = fopen("rucsac.in", "r");
g = fopen("rucsac.out", "w");
fscanf(f, "%d %d", &N, &G);
for (int i = 0; i < N; i++)
{
fscanf(f, "%d %d", &W[i], &P[i]);
}
generateSubsets(W, P, subset, N, G, 0, 0, 0);
fprintf(g, "%d", maxProfit);
fclose(f);
fclose(g);
return 0;
}