g6-07956. 一维边界 未做

小杨有 $T$ 组互相独立的询问，每组都是同一个问题：给出 $n$ 件物品，第 $i$ 件重 $w_i$、价值 $v_i$，背包容量为 $V$，每件物品至多选一次，求最大总价值。数据中混着三种情况：有的组 $V=0$；有的组所有物品都装不下；还有的组里存在重量恰好等于 $V$ 的物品。

第一行一个整数 $T$。

对于每组：第一行两个整数 $n,V$；接下来 $n$ 行，每行两个整数 $w_i,v_i$。

每组一行，一个整数。

输入 1

4
2 0
5 10
3 7
1 8
9 100
3 10
6 60
5 45
5 45
2 8
8 50
4 30

输出 1

0
0
90
50

组 3 选第 2、3 件（重 10）得 90；组 4 两件合重 12 超容，取较优的单件（8,50）。

$1\le T\le 100$，$1\le n\le 100$，$0\le V\le 1000$，$1\le w_i,v_i\le 1000$。