401679: GYM100513 D Data Center

The startup "Booble" has shown explosive growth and now it needs a new data center with the capacity of m petabytes. Booble can buy servers, there are n servers available for purchase: they have equal price but different capacities. The i-th server can store a_i petabytes of data. Also they have different energy consumption — some servers are low voltage and other servers are not.

Booble wants to buy the minimum number of servers with the total capacity of at least m petabytes. If there are many ways to do it Booble wants to choose a way to maximize the number of low voltage servers. Booble doesn't care about exact total capacity, the only requirement is to make it at least m petabytes.

The first line contains two integer numbers n and m (1 ≤ n ≤ 2·10⁵, 1 ≤ m ≤ 2·10¹⁵) — the number of servers and the required total capacity.

The following n lines describe the servers, one server per line. The i-th line contains two integers a_i, l_i (1 ≤ a_i ≤ 10¹⁰, 0 ≤ l_i ≤ 1), where a_i is the capacity, l_i = 1 if server is low voltage and l_i = 0 in the opposite case.

It is guaranteed that the sum of all a_i is at least m.

Print two integers r and w on the first line — the minimum number of servers needed to satisfy the capacity requirement and maximum number of low voltage servers that can be bought in an optimal r servers set.

Print on the second line r distinct integers between 1 and n — the indices of servers to buy. You may print the indices in any order. If there are many solutions, print any of them.

4 10
3 1
7 0
5 1
4 1

2 1
4 2

3 13
6 1
6 1
6 1

3 3
1 2 3 

In the first example any pair of servers which includes the server 2 is a correct output.