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: MEDIUM_HARD
Tags: Complete search

Sorting

Data structures

Greedy algorithms
Skill types: Complete search

Sorting

Data structures

Greedy algorithms
Expected Time Complexity: O(NLOG(N))

Starter code:

Solutions:
from __future__ import print_function
from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n, t) = gil()
a = []
for i in range(n):
	b = gil()
	b.append(i)
	a.append(b)
a.sort(key=lambda x: (x[1], -x[0]))
h = []
ct = 0
for (ai, ti, i) in a:
	if ct + ti > t:
		break
	elif len(h) > ai:
		continue
	ct += ti
	heappush(h, (ai, -ti, i))
	while h and h[0][0] < len(h):
		(ai, ti, i) = heappop(h)
		ct += ti
print(len(h))
print(len(h))
for (_, _, i) in h:
	print(i + 1, end=' ')


from sys import stdin, stdout

def check(k, b, T):
	c = [e for e in b if e[0] >= k]
	if len(c) < k:
		return (False, None)
	first_k_probs = c[:k]
	s = sum([e[1] for e in first_k_probs])
	if s > T:
		return (False, None)
	return (True, first_k_probs)

def solve(n, T, a, t):
	b = []
	for i in range(n):
		b.append((a[i], t[i], i + 1))
	b.sort(key=lambda x: x[1])
	(low, high) = (0, n)
	result = 0
	final_probs = []
	while low <= high:
		mid = (low + high) // 2
		(possible, probs) = check(mid, b, T)
		if possible:
			(result, final_probs) = (mid, probs)
			low = mid + 1
		else:
			high = mid - 1
	return (result, [e[2] for e in final_probs])
(n, T) = (int(x) for x in stdin.readline().split())
a = [0] * n
t = [0] * n
for i in range(n):
	(a[i], t[i]) = (int(x) for x in stdin.readline().split())
(point, probs) = solve(n, T, a, t)
stdout.write('%s\n' % point)
stdout.write('%s\n' % len(probs))
if len(probs) > 0:
	stdout.write('%s\n' % ' '.join([str(x) for x in probs]))


import itertools
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))
listi = sorted(listi, key=lambda x: x[1])
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)))


(n, T) = [int(x) for x in input().split()]
prob = []
vals = [set() for stuff in range(n + 2)]
for i in range(n):
	(a, t) = [int(x) for x in input().split()]
	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
			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()


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)


from collections import deque
import heapq
import sys

def input():
	return sys.stdin.readline().rstrip()
(n, T) = map(int, input().split())
problems = [tuple(map(int, input().split())) for i in range(n)]

def possible(K):
	d = []
	for (a, t) in problems:
		if a >= K:
			d.append(t)
	d.sort()
	if len(d) < K:
		return False
	else:
		return sum(d[:K]) <= T
l = 0
r = n + 1
while r - l > 1:
	med = (r + l) // 2
	if possible(med):
		l = med
	else:
		r = med
print(l)
print(l)
d = []
for (i, (a, t)) in enumerate(problems):
	if a >= l:
		d.append((t, i + 1))
d.sort(key=lambda x: x[0])
ans = [v[1] for v in d[:l]]
print(*ans)


(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]))


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
(N, T) = list(map(int, input().split()))
ta = []
for i in range(N):
	(a, t) = list(map(int, input().split()))
	ta.append((t, a, 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)))


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])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split())
b = []
d = dict()
e = dict()
for i in range(n):
	(a, t) = map(int, input().split())
	b.append([a, t, i + 1])
b.sort(key=lambda x: x[1])
ans = 0
j = 0
curr = 1
currsum = 0
l = 0
while curr <= n:
	if curr - 1 in d.keys():
		currsum -= d[curr - 1]
		l -= e[curr - 1]
	p = 0
	while j < n:
		if b[j][0] >= curr:
			currsum += b[j][1]
			if b[j][0] in d.keys():
				d[b[j][0]] += b[j][1]
				e[b[j][0]] += 1
			else:
				d[b[j][0]] = b[j][1]
				e[b[j][0]] = 1
			l += 1
		if l == curr:
			j += 1
			break
		j += 1
	if j <= n and l == curr and (currsum <= k):
		ans += 1
	else:
		break
	curr += 1
c = []
j = 0
l = 0
while j < n:
	if l == ans:
		break
	if b[j][0] >= ans:
		c.append(b[j][2])
		l += 1
	j += 1
print(ans)
print(ans)
print(*c)


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

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 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))
		exit()
	i += 1


import sys
import operator
import itertools
(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))
listi = sorted(listi, key=lambda x: x[1])
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)
print(max_score)
print(max_score)
print(*list(itertools.islice((idx + 1 for (a, t, idx) in listi if a >= max_score), max_score)))


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()
		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()
	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
if ans == 0:
	print(0)
	print(0)
	print('')
	return
l = get(arr, ans)
print(len(l))
print(len(l))
print(*l)


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
		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
	(res, res_arry) = solve(nums, t, tasks)
	print(res)
	print(res)
	stdout.write(' '.join(map(str, res_arry)))
	stdout.write('\n')
main()


import os
import collections

def ints():
	bytes = bytearray()
	while True:
		buffer = os.read(0, 1024)
		if len(buffer) == 0:
			break
		bytes.extend(buffer)
	array = collections.deque(map(int, bytes.split()))
	return array

def one_pass(pass_num):
	global ans_k, ans_b
	b_time = b_count = 0
	c_time = [0] * (n + 1)
	c_count = [0] * (n + 1)
	k = 1
	for i in a:
		if b_count < k:
			if value(i) >= k:
				b_count += 1
				b_time += time(i)
				c_count[value(i)] += 1
				c_time[value(i)] += time(i)
				if pass_num == 2 and ans_k and (value(i) >= ans_k):
					ans_b.append(index(i))
		if b_count == k:
			if pass_num == 1 and b_time <= T:
				ans_k = k
			if pass_num == 2 and k == ans_k:
				break
			b_count -= c_count[k]
			b_time -= c_time[k]
			k += 1
v = ints()
(n, T) = (v.popleft(), v.popleft())
a = []
for i in range(n):
	(k, t) = (v.popleft(), v.popleft())
	a.append((i + 1, k, t))
index = lambda x: x[0]
value = lambda x: x[1]
time = lambda x: x[2]
a.sort(key=time)
ans_k = 0
ans_b = []
one_pass(1)
one_pass(2)
print(ans_k)
print(ans_k)
print(' '.join(map(str, ans_b)))


def get_answer(a, mid, t, return_ans=False):
	left_time = t
	total_taken = 0
	if return_ans:
		ans = []
	for i in range(len(a)):
		if a[i][0] < mid:
			continue
		if a[i][1] <= left_time:
			total_taken += 1
			if return_ans:
				ans.append(a[i][2])
			left_time -= a[i][1]
		else:
			break
		if total_taken == mid:
			break
	if return_ans:
		return ans
	if total_taken == mid:
		return True
	else:
		return False
from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)
(n, t) = list(map(int, input().split()))
a = []
for i in range(n):
	a.append(list(map(int, input().split())) + [i + 1])
a = sorted(a, key=lambda x: x[1])
l = 0
r = n
while r - l > 1:
	mid = (r + l) // 2
	ans = get_answer(a, mid, t)
	if ans:
		l = mid
	else:
		r = mid
ans = get_answer(a, r, t)
if ans:
	case = r
else:
	case = l
final_ans = get_answer(a, case, t, return_ans=True)
print(str(len(final_ans)))
print('\n')
print(str(len(final_ans)))
print('\n')
s = ' '.join(map(str, final_ans))
print(s)