Codeforces 3B Lorry

English

Desc

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

中文

简介

一群游客将要去皮划艇和双体船游览。一辆租用的货车已经到达船厂，将皮划艇和双体船带到出发点。众所周知，所有皮划艇都具有相同的尺寸（并且每个皮艇占据1立方米的空间），所有双体船的大小相同，但比皮划艇大2倍（占据2立方米）。

每种载体具有特定的承载能力，应该注意的是，看起来相同的水性载体具有不同的承载能力。知道货车体积和船厂水车辆清单（每种类型和承载能力都是已知的），找出可以在卡车上采集的这种车辆，具有最大总承载能力。货车的车身体积可以有效利用，也就是说，您可以随时将货车放置在不超过卡车车身剩余空间的水上车辆上。

让你求出卡车装最多的水性载体的同时达到最大载重量。

输入格式

第一行包含一对整数的 n and v (1 ≤ n ≤ 105; 1 ≤ v ≤ 109),，其中n是水性载体（皮划艇和双体船）在船库的数量，v是的卡车车身体积货车立方米。下面n行包含有关水性车辆信息，这是一个对数 ti, pi (1 ≤ ti ≤ 2; 1 ≤ pi ≤ 104), 其中ti是车辆类型（1 - 皮划艇，2 - 双体船），pi是其承载能力。水上车辆按照输入档案的顺序排列。

输出格式

在第一行打印集合的最大可能承载能力。在第二行中，打印由构成最佳集合的车辆数量组成的字符串。如果答案不是唯一的，请打印其中的任何一个。

测试用例

测试输入

3 2
1 2
2 7
1 3

测试输出

7
2