You are preparing for an exam on scheduling theory. The exam will last for exactly T milliseconds and will consist of n problems. You can either solve problem i in exactly t_{i} milliseconds or ignore it and spend no time. You don't need time to rest after solving a problem, either.

Unfortunately, your teacher considers some of the problems too easy for you. Thus, he assigned an integer a_{i} to every problem i meaning that the problem i can bring you a point to the final score only in case you have solved no more than a_{i} problems overall (including problem i).

Formally, suppose you solve problems p_1, p_2, ..., p_{k} during the exam. Then, your final score s will be equal to the number of values of j between 1 and k such that k ≤ a_{p}_{j}.

You have guessed that the real first problem of the exam is already in front of you. Therefore, you want to choose a set of problems to solve during the exam maximizing your final score in advance. Don't forget that the exam is limited in time, and you must have enough time to solve all chosen problems. If there exist different sets of problems leading to the maximum final score, any of them will do.


-----Input-----

The first line contains two integers n and T (1 ≤ n ≤ 2·10^5; 1 ≤ T ≤ 10^9) — the number of problems in the exam and the length of the exam in milliseconds, respectively.

Each of the next n lines contains two integers a_{i} and t_{i} (1 ≤ a_{i} ≤ n; 1 ≤ t_{i} ≤ 10^4). The problems are numbered from 1 to n.


-----Output-----

In the first line, output a single integer s — your maximum possible final score.

In the second line, output a single integer k (0 ≤ k ≤ n) — the number of problems you should solve.

In the third line, output k distinct integers p_1, p_2, ..., p_{k} (1 ≤ p_{i} ≤ n) — the indexes of problems you should solve, in any order.

If there are several optimal sets of problems, you may output any of them.


-----Examples-----
Input
5 300
3 100
4 150
4 80
2 90
2 300

Output
2
3
3 1 4

Input
2 100
1 787
2 788

Output
0
0


Input
2 100
2 42
2 58

Output
2
2
1 2



-----Note-----

In the first example, you should solve problems 3, 1, and 4. In this case you'll spend 80 + 100 + 90 = 270 milliseconds, falling within the length of the exam, 300 milliseconds (and even leaving yourself 30 milliseconds to have a rest). Problems 3 and 1 will bring you a point each, while problem 4 won't. You'll score two points.

In the second example, the length of the exam is catastrophically not enough to solve even a single problem.

In the third example, you have just enough time to solve both problems in 42 + 58 = 100 milliseconds and hand your solutions to the teacher with a smile.

Difficulty: interview

Starter code:

Solutions:
# -*- coding: utf-8 -*-
"""
Created on Mon Jan  8 10:20:50 2018

@author: yanni
"""

#import random

n, T = [int(x) for x in input().split()]
#n, T = [100000,10000*10000]
prob = []
vals = [set() for stuff in range(n+2)]
for i in range(n):
    a, t = [int(x) for x in input().split()]
    #a = random.randint(1,n)
    #t = random.randint(1, 10000)
    prob.append((i+1,a,t))
prob.sort(key = lambda tup: tup[2])
currindex = 0
maxindex = -1
solve = set()
mem = set()
timeleft = T
target = 1

for currindex in range(n):
    i, a, t = prob[currindex]
    if (timeleft < t):
        break
    if (timeleft >= t and a >= target):
        vals[a].add(currindex)
        solve.add(currindex)
        timeleft -= t
        if (len(solve) == target):
            maxindex = currindex
            #print(target)
            for p in vals[target]:
                solve.remove(p)
                timeleft += prob[p][2]
            target += 1

bestsolve = solve | vals[target-1]
solvelist = [x for x in bestsolve if x<=maxindex]
target = len(solvelist)
print(target)
print(target)
for p in solvelist:
    print(prob[p][0], end=" ")
print()

n, t = list(map(int, input().split()))
ts = []
for i in range(n):
    a,c = list(map(int, input().split()))
    ts.append((a,c, i))
ts = sorted(ts, key=lambda x: x[1])
ans = 0
ptr = 0
hc = {}
hs = {}
csize = 0
ctime = 0
for i in range(n):
    n_ans = ans + 1
    if n_ans - 1 in hc:
        csize -= hc[n_ans-1]
        ctime -= hs[n_ans-1]
    fail = False
    while csize < n_ans:
        if ptr == n:
            fail=True
            break
        a, c, num = ts[ptr]
        if a >= n_ans:
            csize += 1
            ctime += c
            if a not in hc:
                hc[a] = 0
            hc[a] += 1
            if a not in hs:
                hs[a] = 0
            hs[a] += c

        ptr += 1
        if ctime > t:
            fail = True
            break
    if fail:
        break
    else:
        ans = n_ans

print(ans)
print(ans)
tks = []
for i in range(ptr):
    if len(tks) == ans:
        break
    if ts[i][0] >= ans:
        tks.append(ts[i][2])

print(' '.join([str(i+1) for i in tks]))


# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 1/11/18

"""

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

N, T = list(map(int, input().split()))
#
# N, T = 200000, 1000000000

ta = []
for i in range(N):
  a, t = list(map(int, input().split()))
  ta.append((t, a, i+1))
  # ta.append((10000, 200000, i+1))

ta.sort()


score = 0
solvedCount = 0
aks = []
heapq.heapify(aks)
sc = collections.defaultdict(list)
for i in range(N):
  t, a, _ = ta[i]
  if T < t:
    break

  T -= t
  solvedCount += 1

  sc[a].append((t, i))
  heapq.heappush(aks, a)
  removed = []
  while aks and aks[0] < solvedCount:
    k = heapq.heappop(aks)
    removed.append(k)
    v = sc[k]
    solvedCount -= len(v)
    for _, j in v:
      T += ta[j][0]
    del sc[k]

  score = max(score, solvedCount)


print(score)
print(score)

vta = [(t, a, i) for t, a, i in ta if a >= score]
vta.sort()
ans = [i for _, _, i in vta[:score]]
print(" ".join(map(str, ans)))




# -*- coding: utf-8 -*-
"""
Created on Fri Jan 12 18:46:09 2018

@author: Sand Boa
"""

import sys
import operator  # itemgetter
import itertools  # islice

def __starting_point():
    n, T = list(map(int,input().split()))
    listi = []
    for i in range(n):
        a,b = list(map(int,input().split()))
        listi.append((a,b,i))
    #print(listi)
    listi = sorted(listi, key=lambda x: x[1])
    #print(listi)
    time = [0] * (n + 1)
    count = [0] * (n + 1)
    time_sum = 0
    count_sum = 0
    k = 1

    for (a, t, ind) in listi:
        if k <= a:
            time[a] += t
            time_sum += t
            if time_sum > T:
                break

            count[a] += 1
            count_sum += 1
            if count_sum == k:
                count_sum -= count[k]
                time_sum -= time[k]
                k += 1

    max_score = max(count_sum, k - 1)
    #max_score = count_sum

    print (max_score)
    print (max_score)
    print((*list(itertools.islice(
        (idx + 1 for (a, t, idx) in listi if a >= max_score),
        max_score
    ))))
    #print(listi)
    '''for a, t, idx in listi:
        if idx > max_score:
            print(idx,sep=" ")
            '''
    #print(idx+1 for  in listi )

__starting_point()

# -*- coding: utf-8 -*-
"""
Created on Fri Jan 12 18:46:09 2018

@author: Sand Boa
"""
import itertools

def __starting_point():
    n:int
    T:int
    n, T = list(map(int,input().split()))
    listi:list = []
    tsum:int = 0
    csum:int = 0
    k = 1
    a:int
    b:int
    for i in range(n):
        a,b = list(map(int,input().split()))
        listi.append((a,b,i))
    #print(listi)
    listi = sorted(listi, key=lambda x: x[1])
    #print(listi)
    time:list = [0] * (n + 1)
    count:list = [0] * (n + 1)
    for (a, t, ind) in listi:
        if k <= a:
            tsum += t
            time[a] += t
            if tsum > T:
                break
            count[a] += 1
            csum += 1
            if csum == k:
                csum -= count[k]
                tsum -= time[k]
                k += 1
    max_score = max(csum, k - 1)
    print (max_score,max_score,sep='\n')
    print(*list(itertools.islice(
        (idx + 1 for (a, t, idx) in listi if a >= max_score),
        max_score
    )))
    #print(listi)
    '''for a, t, idx in listi:
        if idx > max_score:
            print(idx,sep=" ")
            '''
    #print(idx+1 for  in listi )
      	 		 	  			      		  	 		
__starting_point()

# -*- coding: utf-8 -*-
"""
Created on Fri Jan 12 18:46:09 2018

@author: Sand Boa
"""
import itertools

def __starting_point():
    n:int
    T:int
    n, T = list(map(int,input().split()))
    listi:list = []
    tsum:int = 0
    csum:int = 0
    k:int
    k = 1
    a:int
    b:int
    t:int
    ind:int
    for i in range(n):
        a,b = list(map(int,input().split()))
        listi.append((a,b,i))
    #print(listi)
    listi = sorted(listi, key=lambda x: x[1])
    #print(listi)
    time:list = [0] * (n + 1)
    count:list = [0] * (n + 1)
    for (a, t, ind) in listi:
        if k <= a:
            tsum += t
            time[a] += t
            if tsum > T:
                break
            count[a] += 1
            csum += 1
            if csum == k:
                csum -= count[k]
                tsum -= time[k]
                k += 1
    max_score:int = max(csum, k - 1)
    print (max_score,max_score,sep='\n')
    print(*list(itertools.islice((idx + 1 for (a, t, idx) in listi if a >= max_score),max_score)))


				    						    	 	  	 			 	
__starting_point()

from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
# M = mod = 998244353
def factors(n):return sorted(list(set(reduce(list.__add__,([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))))
# def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split(' ')]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n').split(' ')]
def li3():return [int(i) for i in input().rstrip('\n')]


n,L = li()
l = []
for i in range(n):
    l.append(li())

index = defaultdict(list)
for ind,i in enumerate(l):
    index[tuple(i)].append(ind + 1)
# print(index)
l.sort(key = lambda x:x[1])
d = defaultdict(list)
# print(l)

ans = i = tot = currpoints = 0
anspattern = []
he = []
# print(L)
while i < n:
    # print(l[i])
    if l[i][1] + tot <= L:
        tot += l[i][1]
        heapq.heappush(d[l[i][0]],l[i][1])
        currpoints += 1

        if len(d[l[i][0]]) == 1:
            heapq.heappush(he,l[i][0])
        # i += 1
    # print(he,d,currpoints,tot)
    while len(he) and currpoints > he[0]:
        temp = heapq.heappop(he)
        tot -= heapq.heappop(d[temp])
        currpoints -= 1
        if len(d[temp]):heapq.heappush(he,temp)
    
    if currpoints > ans:
        # print('ans change : ',ans,currpoints,anspattern)
        ans = currpoints
        # anspattern = he[:]
        # for k in he:
        #     for j in d[k]:
        #         anspattern.append(index[tuple([k,j])])
        # print('chengedans : ',ans,currpoints,anspattern)
    
        
    i += 1
i = tot = currpoints = 0
he = []
d = defaultdict(list)

while i < n:
    # print(l[i])
    if l[i][1] + tot <= L:
        tot += l[i][1]
        heapq.heappush(d[l[i][0]],l[i][1])
        currpoints += 1

        if len(d[l[i][0]]) == 1:
            heapq.heappush(he,l[i][0])
        # i += 1
    # print(he,d,currpoints,tot)
    while len(he) and currpoints > he[0]:
        temp = heapq.heappop(he)
        tot -= heapq.heappop(d[temp])
        currpoints -= 1
        if len(d[temp]):heapq.heappush(he,temp)
    
    if currpoints == ans:
        anspattern = []
        for i in he:
            for j in d[i]:
                anspattern.append(index[tuple([i,j])][-1])
                index[tuple([i,j])].pop()
        print(ans)
        print(len(anspattern))
        print(*sorted(anspattern))
        return
        # print('ans change : ',ans,currpoints,anspattern)
        ans = currpoints
        # anspattern = he[:]
        # for k in he:
        #     for j in d[k]:
        #         anspattern.append(index[tuple([k,j])])
        # print('chengedans : ',ans,currpoints,anspattern)
    
        
    i += 1

from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
# M = mod = 998244353
def factors(n):return sorted(list(set(reduce(list.__add__,([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))))
# def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split(' ')]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n').split(' ')]
def li3():return [int(i) for i in input().rstrip('\n')]


n,L = li()
l = []
for i in range(n):
    l.append(li())

index = defaultdict(list)
for ind,i in enumerate(l):
    index[tuple(i)].append(ind + 1)

l.sort(key = lambda x:x[1])
d = defaultdict(list)

ans = i = tot = currpoints = 0
anspattern = []
he = []

while i < n:
    
    if l[i][1] + tot <= L:
        tot += l[i][1]
        heapq.heappush(d[l[i][0]],l[i][1])
        currpoints += 1

        if len(d[l[i][0]]) == 1:
            heapq.heappush(he,l[i][0])
        
    
    while len(he) and currpoints > he[0]:
        temp = heapq.heappop(he)
        tot -= heapq.heappop(d[temp])
        currpoints -= 1
        if len(d[temp]):heapq.heappush(he,temp)
    
    if currpoints > ans:
        ans = currpoints
        
    i += 1
i = tot = currpoints = 0
he = []
d = defaultdict(list)

while i < n:
    
    if l[i][1] + tot <= L:
        tot += l[i][1]
        heapq.heappush(d[l[i][0]],l[i][1])
        currpoints += 1

        if len(d[l[i][0]]) == 1:
            heapq.heappush(he,l[i][0])
    
    while len(he) and currpoints > he[0]:
        temp = heapq.heappop(he)
        tot -= heapq.heappop(d[temp])
        currpoints -= 1
        if len(d[temp]):heapq.heappush(he,temp)
    
    if currpoints == ans:
        anspattern = []
        for i in he:
            for j in d[i]:
                anspattern.append(index[tuple([i,j])][-1])
                index[tuple([i,j])].pop()
        print(ans)
        print(len(anspattern))
        print(*sorted(anspattern))
        return
    i += 1

# https://codeforces.com/contest/913/problem/D
import heapq
from heapq import heappush as push_
from heapq import heappop  as pop_

class heapT():
    def __init__(self, T):
        self.Q     = []
        self.curT  = 0
        self.maxT  = T
        self.his   = []
        
    def push(self, t, index):
        push_(self.Q, (-t, index))
        self.his.append(index)
        self.curT += t
        
        while self.curT > self.maxT:
            self.pop()
            
    def pop(self):
        t, ind     = pop_(self.Q)
        self.his.append(ind) 
        self.curT -= t * -1
        
    def normalize(self, length):
        while len(self.Q) > length:
            self.pop()

def solve(a, n, T):
    a    =  sorted(a, key=lambda x:x[0], reverse=True) 
    H    =  heapT(T)

    max_ = -1
    pos  = None
    
    for ak, t, ind in a:
        H.push(t, ind)
        H.normalize(ak)
    
        if len(H.Q) >  max_:
            max_ = len(H.Q)
            pos  = len(H.his)  
            
    d = {}
    if pos is not None:
        for x in H.his[:pos]:
            if x not in d:
                d[x] = 1
            else:
                del d[x]

    if len(d) > 0:
        print(len(d))
        print(len(d))
        print(' '.join([str(x+1) for x in d]))
    else:
        print('0'+'\n'+'0')

n, T =  list(map(int, input().split()))
a    =  [list(map(int, input().split())) + [_] for _ in range(n)]
solve(a, n, T)

#5 300
#3 100
#4 150
#4 80
#2 90
#2 300        

#7 100
#5 30
#5 40
#6 20
#2 50 
#2 40
#3 10
#4 10

#2 100
#1 787
#2 788


import sys
import math
from collections import defaultdict,deque
import heapq
def search(arr,points,t):
    l=[]
    n=len(arr)
    cnt=0
    for i in range(n):
        if arr[i][0]>=points:
            l.append(arr[i][1])
            cnt+=1
    if cnt>=points:
        l.sort()
        #print(l,'l')
        if sum(l[:points])<=t:
            return True
    return False
def get(arr,points):
    n=len(arr)
    l=[]
    for i in range(n):
        if arr[i][0]>=points:
            l.append([arr[i][1],arr[i][2]+1])
    l.sort()
    #print(l,'get')
    res=[]
    for i in range(points):
        res.append(l[i][1])
    return res
n,t=list(map(int,sys.stdin.readline().split()))
dic=defaultdict(int)
arr=[]
for i in range(n):
    a,b=list(map(int,sys.stdin.readline().split()))
    arr.append([a,b,i])
low,high=0,n
ans=0
while low<=high:
    mid=(low+high)//2
    if search(arr,mid,t):
        ans=max(ans,mid)
        low=mid+1
    else:
        high=mid-1
#print(ans)
if ans==0:
    print(0)
    print(0)
    print('')
    return
l=get(arr,ans)
print(len(l))
print(len(l))
print(*l)



import sys
input=sys.stdin.readline
def fun(k):
    nonlocal li,t
    tem=[]
    count=0
    for i in li:
        if(i[0]>=k):
            tem.append(i)
            count+=1
    if(count>=k):
        ans=0
        for i in range(k):
            ans+=tem[i][1]
        if(ans<=t):
            return True
        else:
            return False
    else:
        return False
                  
n,t=map(int,input().split())
li=[]
for _ in range(n):
    li.append(list(map(int,input().split()))+[_])
li.sort(key=lambda x:x[1])
l=0
r=n
while(r-l>1):
    mid=(l+r)//2
    if(fun(mid)):
        l=mid
    else:
        r=mid
fin=0
for i in range(l,r+1):
    if(fun(i)):
        fin=i
print(fin)
print(fin)
tem=[]
for i in range(n):
    if(li[i][0]>=fin):
        tem.append(li[i][2]+1)
print(*tem[:fin])

from sys import stdin, stdout
import sys
input=sys.stdin.readline

def solve(n, t, tasks):
    lo = 0
    hi = n

    res = []
    curr_res = 0

    tasks.sort(key=lambda x: x[1])

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        # check if we can make mid.
        valid_tasks = []
        for i in tasks:
            if i[0] >= mid:
                valid_tasks.append(i)
        
        can_do = False

        curr_sum = 0
        total_used = 0
        r = []
        for i in valid_tasks:
            curr_sum += i[1]
            total_used += 1
            r.append(i[2])
            if curr_sum > t:
                break
            elif total_used >= mid:
                can_do = True
                curr_res = mid
                res = r
                break
        if can_do:
            lo = mid + 1
        else:
            hi = mid - 1
    return curr_res, res
        





def main():
    n, t = (int(x) for x in input().split(" "))
    tasks = []
    nums = n
    idx = 1
    while n:
        a_i, t_i = (int(x) for x in input().split(" "))
        tasks.append((a_i, t_i, idx))
        idx += 1
        n -= 1
    # print(nums, t, tasks)
    res, res_arry = solve(nums, t, tasks)
    print(res)
    print(res)
    stdout.write(" ".join(map(str, res_arry)))
    stdout.write("\n")


def __starting_point():
    main()

__starting_point()