Problem: 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.

Input

The first line contains a pair of integer numbers n and v (1 ≤ n ≤ 105; 1 ≤ v ≤ 109), 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 ti, pi (1 ≤ ti ≤ 2; 1 ≤ pi ≤ 104), where ti is the vehicle type (1 – a kayak, 2 – a catamaran), and pi is its carrying capacity. The waterborne vehicles are enumerated in order of their appearance in the input file.

Output

In the first line print the maximum possible carrying capacity of the set. In the second line print a string consisting of the numbers of the vehicles that make the optimal set. If the answer is not unique, print any of them.

Examples

Input

3 2
1 2
2 7
1 3


Output

7
2

Solution (in PYTHON):

Solution:
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import time
import sys
import io
start = time.clock()

def main():
    n,v=map(int, raw_input().split())
    pool=[]
    inset=[]
    for i in xrange(1, n+1):
        t,p=[int(x) for x in sys.stdin.readline().split()]
#        t,p=[int(x) for x in raw_input().split()]
        pool.append((p*1.0/t, p, t, i))
    pool.sort(key=lambda item: item[0], reverse=True)
#    print pool
    sumary=0
#    for i in xrange(0, n):
    for i in xrange(n):
#下に出てくるvの減算と連動。0以下で中断させる。
        if v<=0: break
#        x=pool[i]
#        sumary+=x[1]
#価値を足す
        sumary+=pool[i][1]
#        v-=x[2]
#v(使える最大の重さ)から使った重さを引く
        v-=pool[i][2]
#        inset.append(x[3])
#使ったものの元のリストでの順番を記録する
        inset.append(pool[i][3])
    if v==-1:
#フラグをFalseにしておく
        found=False
#poolリストの中を加算した順に遡って探す
#iは加算した最終地点で、jは-1から減算されていく
        for j in xrange(-1, -i-1, -1):
#重さ1のものがあればTrueフラグにして終わる
            if pool[i+j][2]==1:
                found=True
                break
#foundフラグがFalseの時はjを-1にする
        if not found: j=-1
#重さ1のものを使ってた時は最後に使われた重さ1の(より優先度が低い)ものが取り除かれる
#重さ1のものを使ってなかった時は最後に加算されたものが取り除かれる
#価値の合計をその1へ代入
        sumary1=sumary-pool[i+j][1]
        found=False
#使える重さが0以下になって中断したところから開始
        for k in xrange(i, n):
#優先度の低い方へ見ていき重さ1のものがあればTrueにして中断
            if pool[k][2]==1:
                found=True
                break
#最後に加算されたものが取り除かれる
#価値の合計をその2へ代入
        sumary2=sumary-pool[i-1][1]
        if found:
#重さ1で発見されたものを足す
            sumary2+=pool[k][1]
        if sumary1>sumary2:
#その1の方が価値が高ければ代入して、使ってるものリストからj番目を取り除く
            sumary=sumary1
            inset.pop(j)
        else:
#その2の方を代入して、末尾を取り除く
            sumary=sumary2
            inset.pop()
            if found:
#使った物リストへk番目の順番を追加する
                inset.append(pool[k][3])
    sys.stdout.write(str(sumary))
    sys.stdout.write('\n')
    sys.stdout.write(' '.join(str(x) for x in inset))

if __name__=='__main__':
    main()