// Based on "Algorithms in C, Third Edition", and
// "Algorithms in Java, Third Edition", Robert Sedgewick

// 0/1 (divisible) knapsack by dynamic programming
// where there is an unlimited number of each item type.
// CSE 2320 Notes 7 and Sedgewick 5.3

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

int  unknown=(-1);

typedef struct {
  int val,size;
} item;

int N,m;
item *items;
int *maxKnown;
item *itemKnown;

// From Sedgewick
int knap(int M,int level)
{ int i, space, max, maxi = 0, t;
  for (i=0;i<level;i++)
    printf(".");
  if (maxKnown[M] != unknown)
  {
    printf("Reusing knap(%d)=%d\n",M,maxKnown[M]);
    return maxKnown[M];
  }
  printf("Start knap(%d)\n",M);
  for (i = 0, max = 0; i < N; i++)
    if ((space = M-items[i].size) >= 0)
      if ((t = knap(space,level+1) + items[i].val) > max)
        { max = t; maxi = i; }
  maxKnown[M] = max; itemKnown[M] = items[maxi];
  for (i=0;i<level;i++)
    printf(".");
  printf("Finish knap(%d)\n",M);
  return max;     
}

int main()
{
int i;
int count,leftoverVal;
int leftoverSize;

// Get input sequence
scanf("%d",&N);     // Number of input item types
scanf("%d",&m);     // Maximum sum of weights in knapsack
items=(item*) malloc(N*sizeof(item));  // Input items
if (!items)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
for (i=0;i<N;i++)
{
  scanf("%d",&items[i].size);
  scanf("%d",&items[i].val);
}

// Initialize table for DP
maxKnown=(int*) malloc((m+1)*sizeof(int));
itemKnown=(item*) malloc((m+1)*sizeof(item));
if (!maxKnown || !itemKnown)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
for (i=0;i<=m;i++)
  maxKnown[i]=unknown;

// Since knap() uses memoization, a bottom-up loop is not needed.
printf("Maximum for %d is %d\n",m,knap(m,0));

// Output the input set
printf("  i size val\n");
printf("------------\n");
for (i=0;i<N;i++)
  printf("%3d  %3d %3d\n",i,items[i].size,items[i].val);

// Output the DP table
printf("  i max size val\n");
printf("----------------\n");
for (i=0;i<=m;i++)
  if (maxKnown[i]>0)
    printf("%3d %3d  %3d %3d\n",i,maxKnown[i],itemKnown[i].size,
      itemKnown[i].val);

printf("Solution has value %d:\n",maxKnown[m]);
printf("  i size  val\n");
printf("-------------\n");
count=0;
leftoverVal=maxKnown[m];
leftoverSize=m;
while (leftoverVal>0)
{
  count++;
  printf("%3d  %3d  %3d\n",
    count,itemKnown[leftoverSize].size,itemKnown[leftoverSize].val);
  leftoverVal-=itemKnown[leftoverSize].val;
  leftoverSize-=itemKnown[leftoverSize].size;
}
printf("Unused capacity %d\n",leftoverSize);

free(items);
free(maxKnown);
free(itemKnown);
}