Background

Special for beginners, ^_^

Description

有 n 件物品, 每件物品有一个价值和一个重量，分别记为： $v_1v_2 …v_n w_1w_2 …w_n$其中所有的 重量wi 均为整数。 现有一个背包，其最大载重量为C，要求从这n件物品中任取若干件（这些物品要么被装入要么被留下）。问背包中装入哪些物品可使得所装物品的价值和最大？

Format

Input

第1行：2个整数n(1<=n<=1000)和C(1<=C<=10000)，分别表示物品的件数和背包的最大载重量。
第2-n+1行：每行2个用空格分开的整数，第i+1行的整数表示第i件物品的重量wi和价值vi($1\leq w_i,v_i \leq10000$)。

Output

第1行：1个整数，表示背包所能装下的物品的最大总价值。
第2-？行：每行3个用空格分开的整数，$i$; $w_i$;$v_i$，分别表示最优解中的物品的编号、重量和价值。

Samples

4 5
2 3
3 4
4 5
5 6

7
1 2 3
2 3 4

Limitation

1s, 1024KiB for each test case.