说明

央视有一个大型娱乐节目—购物街，舞台上模拟超市大卖场，有很多货物，每个嘉宾分配一个购物车，可以尽情地装满购物车，购物车中装的货物价值最高者取胜。假设有$n$个物品和1个购物车，每个物品$i$对应价值为$v_i$，重量$w_i$，购物车的容量为$W$（你也可以将重量设定为体积）。每个物品只有一件，要么装入，要么不装入，不可拆分。如何选取物品装入购物车，使购物车所装入的物品的总价值最大？要求输出最优值(装入的最大价值)和最优解（装入了哪些物品)。

输入格式

第一行是一个整型数$m(m<100)$表示共有$m$组测试数据。

每组测试数据第一行输入，$n$ 和 $W（1 <= n <=40，1 <= W <= 10^{15}）$，接下来有$n$行，每行输入两个数，代表第$i$个物品的重量$w_i$ 和价值 $v_i（1 <= w_i，v_i <= 10^{15}）$。

输出格式

对于每一组输入，输出满足题意的最大价值和最优解。

每组的输出占一行。

样例

2
5 10
2 6
5 3
4 5
2 4
3 6
4 52
12 13
10 24
22 13
9 24

17
61

来源

《趣学算法》6.2节