Description

已知n种物品和一个可容纳c重量的背包，物品i的重量为wi，产生的效益为pi。在装包时物品i可以装入，也可以不装，但不能拆开装。问如何装包，使得装包总效益最大。

Input

输入分多行。
第一行输入两个整数n和c。n表示物品的种数，c表示背包的容量。
接下去的n行每行输入两个整数，每行表示一种物品，这两个整数分别为该种物品的重量wi和产生的效益pi。

Output

输出可以被装包的物品的编号，重量和效益，每种物品占据一行。再另起一行输出总共装包的重量以及获取的最大效益。具体格式见输出样例的说明。物品编号根据输入顺序编排，第一个输入的编号为1，第2个输入的编号为2，依次类推。

Sample Input

6 60
15 32
17 37
20 46
12 26
9 21
14 30

Sample Output

2 17 37
3 20 46
5 9 21
6 14 30
w=60,pmax=134

HINT

Source

NBU OJ