bag.cpp

#include <bits/stdc++.h>
using namespace std;

#define task "BAG"

const int N = 55;
const int M = 105;

int w[N], v[N], dp[N][M];

void chmax(int &a, int b) {
  if (a < b) a = b;
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  freopen(task".INP", "r", stdin );
  freopen(task".OUT", "w", stdout);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> w[i] >> v[i];
  }
  for (int i = 1; i <= n; i++)
  for (int j = 0; j <= m; j++) {
    dp[i][j] = dp[i - 1][j];
    if (j >= w[i]) chmax(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
  }
  cout << dp[n][m] << '\n';
  // phan truy vet
  int i = n, j = m;
  while (i > 0 && j > 0) {
    if (dp[i][j] == dp[i - 1][j]) i--;
    else {
      cout << i << ' ';
      j -= w[i]; // j -= w[i] xong roi moi i-- neu khong se sai
      i--;
    }
  }
  cout << '\n';
  cout << m - j << '\n';
}