A group of tourists is going to kayak and catamaran tour. A rented lorry has arrived to the boat depot to take kayaks and catamarans to the point of departure. It's known that all kayaks are of the same size (and each of them occupies the space of 1 cubic metre), and all catamarans are of the same size, but two times bigger than kayaks (and occupy the space of 2 cubic metres).

Each waterborne vehicle has a particular carrying capacity, and it should be noted that waterborne vehicles that look the same can have different carrying capacities. Knowing the truck body volume and the list of waterborne vehicles in the boat depot (for each one its type and carrying capacity are known), find out such set of vehicles that can be taken in the lorry, and that has the maximum total carrying capacity. The truck body volume of the lorry can be used effectively, that is to say you can always put into the lorry a waterborne vehicle that occupies the space not exceeding the free space left in the truck body.
The first line contains a pair of integer numbers *n* and *v* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>; 1 ≤ *v* ≤ 10<sup class="upper-index">9</sup>), where *n* is the number of waterborne vehicles in the boat depot, and *v* is the truck body volume of the lorry in cubic metres. The following *n* lines contain the information about the waterborne vehicles, that is a pair of numbers *t*<sub class="lower-index">*i*</sub>, *p*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 2; 1 ≤ *p*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">4</sup>), where *t*<sub class="lower-index">*i*</sub> is the vehicle type (1 – a kayak, 2 – a catamaran), and *p*<sub class="lower-index">*i*</sub> is its carrying capacity. The waterborne vehicles are enumerated in order of their appearance in the input file.
# LUOGU_RID: 122316449
from math import inf
import sys
import sys
from collections import defaultdict
from math import inf


# sys.setrecursionlimit(10**8)设置最大递归次数


class FastIO:
    def __init__(self):
        return

    @staticmethod
    def read_int():
        return int(sys.stdin.readline().strip())

    @staticmethod
    def read_float():
        return float(sys.stdin.readline().strip())

    @staticmethod
    def read_ints():
        return map(int, sys.stdin.readline().strip().split())

    @staticmethod
    def read_floats():
        return map(float, sys.stdin.readline().strip().split())

    @staticmethod
    def read_ints_minus_one():
        return map(lambda x: int(x) - 1, sys.stdin.readline().strip().split())

    @staticmethod
    def read_list_ints():
        return list(map(int, sys.stdin.readline().strip().split()))

    @staticmethod
    def read_list_floats():
        return list(map(float, sys.stdin.readline().strip().split()))

    @staticmethod
    def read_list_ints_minus_one():
        return list(map(lambda x: int(x) - 1, sys.stdin.readline().strip().split()))

    @staticmethod
    def read_str():
        return sys.stdin.readline().strip()

    @staticmethod
    def read_list_strs():
        return sys.stdin.readline().strip().split()

    @staticmethod
    def read_list_str():
        return list(sys.stdin.readline().strip())

    @staticmethod
    def st(x):
        return sys.stdout.write(str(x) + '\n')

    @staticmethod
    def lst(x):
        return sys.stdout.write(" ".join(str(w) for w in x) + '\n')

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    def ask(self, lst):
        # CF交互题输出询问并读取结果
        self.lst(lst)
        sys.stdout.flush()
        res = self.read_int()
        # 记得任何一个输出之后都要 sys.stdout.flush() 刷新
        return res

    def out_put(self, lst):
        # CF交互题输出最终答案
        self.lst(lst)
        sys.stdout.flush()
        return

    @staticmethod
    def accumulate(nums):
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        return pre

    @staticmethod
    def get_random_seed():
        # 随机种子避免哈希冲突
        return random.randint(0, 10**9+7)


class Solution:
    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        n, v = ac.read_ints()
        dct = defaultdict(list)
        for i in range(n):
            t, p = ac.read_ints()
            dct[t].append([p, i])
        for x in [1, 2]:
            dct[x].sort(key=lambda it: -it[0])

        m = len(dct[1])
        pre= [0]*(m+1)
        for i in range(m):
            pre[i+1] = pre[i]+dct[1][i][0]

        ans = -inf
        res = [-1, -1]
        cur = 0
        for c2 in range(0, len(dct[2])+1):
            if c2*2 > v:
                break
            if c2:
                cur += dct[2][c2-1][0]
            cur1 = pre[ac.min(v-c2*2, m)]
            if cur1+cur > ans:
                ans = cur1+cur
                res = [ac.min(v-c2*2, m), c2]


        ac.st(ans)
        ac.lst([x for _, x in dct[1][:res[0]]] + [x for _, x in dct[1][:res[1]]])
        return


Solution().main()
