【题目描述】

有 $T$ 组数据。背包容量为 $m$，有 $n$ 件物品。第 $i$ 件大小为 $a_i$、价值为 $b_i$，每件最多选择一次。

求总大小不超过 $m$ 时的最大总价值。

【输入格式】

$T$

$n$   $m$

$a_1$   $b_1$

$\vdots$

【输出格式】

每组输出一行最大价值。

【样例】

2
3 10
6 4
4 5
7 6
2 3
5 2
4 3

9
0

【数据范围】

• $1\le T\le10$
• $1\le n\le100$
• $1\le a_i\le10^7$
• $1\le b_i\le100$
• $0\le m\le10^9$