【题目描述】

有 $T$ 组数据。背包容量为 $m$，有 $n$ 块矿石。第 $i$ 块重量为 $w_i$，价值为 $v_i$。

每块矿石最多选择一次，求总重量不超过 $m$ 时的最大总价值。本题使用搜索或二进制枚举。

【输入格式】

$T$

$n$   $m$

$w_1$   $v_1$

$\vdots$

$w_n$   $v_n$

【输出格式】

每组输出一行最大价值。

【样例】

2
3 5
2 3
3 4
4 8
2 1
2 10
3 20

8
0

【数据范围】

• $1\le T\le100$
• $1\le n\le15$
• $1\le m,w_i,v_i\le1000$