packing.py

cache = None


def memoize(fn):
    global cache

    def helper(w, ts, i):
        if cache[w][i] == -1:
            cache[w][i] = fn(w, ts, i)
        return cache[w][i]
    return helper


@memoize
def eager(w, ts, i):
    if len(ts) < i + 1:
        return 0
    n, s, e = ts[i]
    ne = eager(w, ts, i + 1)
    if w < s:
        return ne
    te = eager(w - s, ts, i + 1) + e
    return max(te, ne)


def collect(rv, me, w, ts, i):
    if len(ts) < i + 1:
        return
    n, s, e = ts[i]
    te = eager(w - s, ts, i + 1) + e
    if te == me and w >= s:
        rv.append(i)
        collect(rv, me - e, w - s, ts, i + 1)
    else:
        collect(rv, me, w, ts, i + 1)


def solv(w, ts):
    global cache
    cache = [[-1] * 101 for i in range(1001)]
    me = eager(w, ts, 0)
    rv = []
    collect(rv, me, w, ts, 0)
    return [me, len(rv), [ts[i][0] for i, t in enumerate(ts) if i in rv]]


if __name__ == "__main__":
    c = int(raw_input())
    for i in xrange(c):
        ts = []
        n, w = [int(i) for i in raw_input().split()]
        for p in xrange(n):
            t = raw_input().split()
            ts.append([t[0], int(t[1]), int(t[2])])
        rv = solv(w, ts)
        print rv[0], rv[1]
        for t in rv[2]:
            print t