KNAPSACK

#define task "KNAPSACK"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e3 + 5;
constexpr ll Inf = 1e17;
int n;
ll dp[N][N * 5];
ll w[N], W, v[N];
pair<ll, ll> f[N * N];

void Read()
{
    cin >> n >> W;

    for (int i = 1; i <= n; ++i)
        cin >> w[i] >> v[i];
}

void Trace_1(int n, int k)
{
    if (n == 0)
        return;

    if (dp[n][k] == dp[n - 1][k])
        Trace_1(n - 1, k);
    else
    {
        Trace_1(n - 1, k - w[n]);
        cout << n << " ";
    }
}

void Sub_1()
{
    fill_n(&dp[0][0], N * N * 5, -Inf);

    dp[0][0] = 0;

    for (int i = 1, sum = w[1]; i <= n; sum += w[++i])
    {
        sum = min(sum, (int)W);
        for (int j = 0; j <= sum; ++j)
        {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            if (j >= w[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
        }
    }

    pair<ll, int> ans({-Inf, 0});

    for (int i = 0; i <= W; ++i)
        ans = max(ans, make_pair(dp[n][i], i));

    cout << ans.first << "\n";

    Trace_1(n, ans.second);
}

#define bit(i, x) (((x) >> (i)) & 1)

void Sub_2()
{

    int m = n / 2;
    int p = n - m;

    struct Val
    {
        ll w, v, mask;

        Val(ll w = 0, ll v = 0, ll mask = 0) : w(w), v(v), mask(mask) {}

        bool operator<(const Val &a) const
        {
            return w < a.w;
        }
    };
    vector<Val> s;

    {
        for (int i = 0; i < (1 << p); ++i)
        {
            ll tmpw(0), tmpv(0);
            for (int j = 0; j < p; ++j)
                if (bit(j, i))
                {
                    tmpw += w[j + m + 1];
                    tmpv += v[j + m + 1];
                }
            if (tmpw <= W)
                s.emplace_back(tmpw, tmpv, i);
        }

        sort(s.begin(), s.end());

        f[0].first = -Inf;
        for (int i = 0; i < (int)s.size(); ++i)
            f[i + 1] = max(f[i], make_pair(s[i].v, s[i].mask));
    }

    pair<ll, ll> ans({-Inf, 0});

    for (int i = 0; i < (1 << m); ++i)
    {
        ll tmpw(0), tmpv(0);
        for (int j = 0; j < m; ++j)
            if (bit(j, i))
            {
                tmpw += w[j + 1];
                tmpv += v[j + 1];
            }

        if (tmpw <= W)
        {
            tmpw = W - tmpw;

            int l = 0, mid, h = s.size() - 1;

            while (l <= h)
            {
                mid = (l + h) / 2;
                if (s[mid].w <= tmpw)
                    l = mid + 1;
                else
                    h = mid - 1;
            }

            ans = max(ans, make_pair(tmpv + f[l].first, i | (f[l].second << m)));
        }
    }

    cout << ans.first << "\n";

    for (int i = 0; i < n; ++i)
        if (bit(i, ans.second))
            cout << i + 1 << " ";
}

void Trace_3(int n, int k)
{
    if (n == 0)
        return;

    if (dp[n][k] == dp[n - 1][k])
        Trace_3(n - 1, k);
    else
    {
        Trace_3(n - 1, k - v[n]);
        cout << n << " ";
    }
}

void Sub_3()
{
    fill_n(&dp[0][0], N * N * 5, Inf);

    dp[0][0] = 0;

    for (int i = 1, sum = v[1]; i <= n; sum += v[++i])
        for (int j = 0; j <= sum; ++j)
        {
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
            if (j >= v[i])
                dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }

    for (int i = 5000; i; --i)
        if (dp[n][i] <= W)
        {
            cout << i << "\n";
            Trace_3(n, i);
            return;
        }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    if (W <= 5000)
        Sub_1();
    else if (n <= 40)
        Sub_2();
    else
        Sub_3();
}