#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <set>
#include <vector>

int v[100];
int c[100];
int p[100];

int idx[100];

int n, v0;

int best[100];
int best_n = 0;
int best_cost = 0;

int curr[100];

struct cmp
{
    bool operator () (int const &a, int const &b) const
    {
        return c[a] * v[b] > c[b] * v[a];
    }
};

void greedy(int n, int vv, int mul)
{
    std::sort(idx, idx + n, cmp());
    std::vector<std::pair<int, int> > swaps;

    for (int tt = 0; tt < 30000 * mul; ++tt)
    {
        int sum_c = 0;
        int sum_v = 0;
        int cnt = 0;
        for (int i = 0; i < n; ++i) 
        {
            int j = idx[i];
            if (sum_v + v[j] <= vv) 
            {
                sum_v += v[j];
                sum_c += c[j];
                curr[cnt++] = j;
            }
        }
        if (sum_c > best_cost)
        {
            std::cout << "[" << tt << "] " << best_cost << " -> " << sum_c << std::endl;
            best_cost = sum_c;
            best_n = cnt;
            for (int i = 0; i < cnt; ++i) 
            {
                best[i] = curr[i];
            }
        }

        for (int i = swaps.size() - 1; i >= 0; --i)
        {
            std::swap(idx[swaps[i].first], idx[swaps[i].second]);        
        }
        swaps.clear();

        do {
            int swap1 = rand() % n;
            int swap2 = rand() % n;
            swaps.push_back(std::make_pair(swap1, swap2));
            std::swap(idx[swap1], idx[swap2]);        
        } while (rand() % 2);
    }
}

int main()
{
    srand(unsigned(time(0)));

    std::ifstream in("knapsack.in");
    in >> n >> v0;
    for (int i = 0; i < n; ++i)
    {
        in >> v[i] >> c[i] >> p[i];
        idx[i] = i;
    }

    std::set<int> pressures;
    for (int i = 0; i < n; ++i)
    {
        pressures.insert(p[i]);
    }

    int mul = n /  pressures.size();
    
    for (std::set<int>::const_iterator it = pressures.begin(); it != pressures.end(); ++it)
    {
        int cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            if (p[i] >= *it)
            {
                idx[cnt++] = i;
            }
        }
        greedy(cnt, v0 + *it, mul);
    }
    
    std::ofstream out("knapsack.out");
    out << best_n << " " << best_cost << std::endl;
    for (int i = 0; i < best_n; ++i)
    {
        out << 1 + best[i] << " ";
    }
    out << std::endl;
    return 0;
}
