// 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

import java.util.Scanner;

public class knapsackTypeRS
{
  static int unknown=(-1);

  static class item
  {
    int val,size;
  }

  static int N,m;
  static item items[];
  static int maxKnown[];
  static item itemKnown[];

  // From Sedgewick
  static int knap(int M)
    { int i, space, max, maxi = 0, t;
      if (maxKnown[M] != unknown) 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; itemKnown[M] = items[maxi];
      return max;     
    }

  public static void main(String[] args)
  {
    // Get input sequence
    Scanner sc=new Scanner(System.in);
    N=sc.nextInt();     // Number of input item types
    m=sc.nextInt();     // Maximum sum of weights in knapsack
    items=new item[N];  // Input items
    for (int i=0;i<N;i++)
    {
      items[i]=new item();
      items[i].size=sc.nextInt();
      items[i].val=sc.nextInt();
    }

    // Initialize table for DP
    maxKnown=new int[m+1];
    itemKnown=new item[m+1];
    for (int i=0;i<=m;i++)
      maxKnown[i]=unknown;

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

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

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

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