// http://www.infoarena.ro/problema/rucsac
// 100 p

#include <fstream>
#include <iostream>
#include <iomanip>

using namespace std;

struct obiect {
  int g, p; // greutatea, profitul
};

obiect a[5001];
int n, G, l, g, p, c, pn, lp, lc, mp[2][10001];
ifstream fi ("rucsac.in");
ofstream fo ("rucsac.out");

/* Ideea de rezolvare:
   Pentru un rucsac de capacitate c, asociem obiectul curent (l), avand greutatea a[lc].g,
   cu varianta optima obtinuta prin plasarea a l-1 obiecte intr-un rucsac cu capacitate c-a[lc].g. */

int main() {
  fi >> n >> G; // numarul de obiecte, capacitatea totala a rucsacului
  for (l = 1; l <= n; l++)
    fi >> a[l].g >> a[l].p;
  lp = 0; lc = 1;
  for (l = 1; l <= n; l++) {            // pentru fiecare obiect
    for (c = 1; c <= G; c++) {          // pentru fiecare capacitate a rucsacului
      if (a[l].g <= c) {                // Obiectul curent incape in rucsac?
        pn = a[l].p + mp[lp][c-a[l].g]; // profitul nou
        if (pn > mp[lp][c])             // Avem profit mai bun folosind obiectul curent?
          mp[lc][c] = pn;               // Retinem profitul nou.
        else {
          mp[lc][c] = mp[lp][c];        // Retinem profitul obtinut cu primele l-1 obiecte.
          fo << l << ' ' << c;
        }
      }
      else
        mp[lc][c] = mp[lp][c];          // Retinem profitul obtinut cu primele l-1 obiecte.
    }
    lp = 1 - lp; lc = 1 - lc;           // Schimbam intre ele liniile.
  }
  fo << mp[lp][G];                      // Am folosit toate obiectele si capacitatea integrala a ruscacului.
  return 0;
}