该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一天一个名字叫小W的海岛船长到了一个非常神秘的宫殿里，他在里面发现了 $n$ 个金块，每个金块价值为 $v[i]$ ，重量 $w[i]$ ，很遗憾，他不能全部带回去，因为他的背包就只可以装的下重量为 $W$ 的东西回去，问最多能带多少价值的东西？

输入格式

第一行输入一个数 $T$ ，表示测试数据数，对于每组测试数据，第一行输入两个数，$n，W$ ，接下来输入 $n$ 行，每行两个数，分别表示该物品的价值和重量

输出格式

最多能带多少价值的东西。

样例

1
5 20
5 8
3 7
7 4
2 6
3 5

15

范围

• $1 \leq T \leq 10$
• $0<$n$≤100000$
• $0≤$W$≤10000$
• $0<w[i],v[i]≤10$