g6-07988. 值域·多测 未做

小杨有 $T$ 个箱子要分别装东西：每个箱子里有 $n$ 件物品，第 $i$ 件重 $w_i$、价值 $v_i$（$v_i\le 100$），每件只有一件，最多拿一次；箱子容量 $V$ 最多可达 $10^9$。请对每个箱子分别求最多能带走多少价值。

第一行一个整数 $T$。

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

每组一行，一个整数。

输入 1

2
2 1000000000
1000000000 100
999999999 100
2 1000000000
1000000000 7
999999999 7

输出 1

100
7

$1\le T\le 5$，$1\le n\le 100$，$1\le V\le 10^9$，$1\le w_i\le 10^9$，$1\le v_i\le 100$。