/*
 * This code is from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 */
#include <stdio.h>
#include <stdlib.h>

#define NMAX 1000
#define CapMAX 10000

typedef struct {int size; int val; } Item;

int knap(int);
void imprima_itens(int);

int n;
Item items[NMAX];

int maxKnown[CapMAX];
Item itemKnown[CapMAX];

int main(int argc, char *argv[])
{
  int cap=atoi(argv[2]), i;

  n=atoi(argv[1]);

  for (i=0; i<n; i++) 
    scanf("%d %d", &items[i].size, &items[i].val);

  for (i=0; i<CapMAX; i++) 
    maxKnown[i]=-1;

  printf("Valor maximo: %d\n", knap(cap));

  imprima_itens(cap);
    
  return 0;
}

int knap(int M)
  { int i, space, max, maxi, t;
    if (maxKnown[M] != -1) return maxKnown[M];
    for (i = 0, max = 0; i < n; i++)
      if ((space = M - items[i].size) >= 0)
        if ((t = knap(space) + items[i].val) > max)
          { max = t; maxi = i; }
    maxKnown[M] = max;
    if (max>0)
      itemKnown[M] = items[maxi];
    return max;     
  }

void imprima_itens(int cap)
{
  if (maxKnown[cap]>0) {
    printf("%d %d\n", itemKnown[cap].size, itemKnown[cap].val);
    imprima_itens(cap - itemKnown[cap].size);
  }
}