from collections import namedtuple

import numpy as np

Item = namedtuple("Item", ["value", "weight"])

def dp_opt_v3(item_count: int, capacity: int, items: list):
    table_bool = np.zeros((item_count + 1, capacity + 1), dtype = np.bool)
    table_small = np.zeros((2, capacity + 1), dtype = np.int32)

    for i in range(item_count):
        v = items[i].value
        w = items[i].weight
        c, p = (i & 1), (~i & 1)

        table_small[c, :w] = table_small[p, :w]

        row1 = table_small[p, w:]
        row2 = table_small[c, :-w] + v

        table_small[c, w:] = np.where(row2 > row1, row2, row1)
        table_bool[i + 1, w:] = np.where(table_small[c, w:] != table_small[p, w:], 1, 0)

    s = []
    w = capacity
    knapsack_val = table_small[-1][-1]

    for i in range(item_count, 0, -1):
        if table_bool[i, w] == 1:
            s.append(1)
            w -= items[i - 1].weight
            i -= 1
        else:
            s.append(0)

    print(table_small)
    del table_bool
    return (knapsack_val, 1, s)

def solve_it(input_data):
    lines = input_data.split('\n')

    firstLine = lines[0].split()
    item_count = int(firstLine[0])
    capacity = int(firstLine[1])

    items = []

    for i in range(1, item_count+1):
        line = lines[i]
        parts = line.split()
        items.append(Item(int(parts[0]), int(parts[1])))

    knapsack = dp_opt_v3(item_count, capacity, items)

    knapsack[2].reverse()
    output_data = f"{knapsack[0]} {knapsack[1]}\n" + " ".join(map(str, knapsack[2]))

    return output_data

if __name__ == "__main__":
    if len(sys.argv) > 1:
        file_location = sys.argv[1].strip()
        with open(file_location, "r") as input_data_file:
            input_data = input_data_file.read()

        print(solve_it(input_data))