程序设计能力实训

1173. 0-1背包问题

单点时限: 2.0 sec

内存限制: 256 MB

已知 $n$ 个物体 $1,2,3,\ldots,n$ 与一个背包。物体 $i$ 的重量为 $W_i > 0$,价值为 $P_i > 0$ $(i=1,2,\ldots,n)$,背包容量为 $M > 0$。

求在不超过背包容量的情况下,使得装进去的物体的价值最高。

输入格式

第一行为一个正整数 $T$,表示有几组测试数据。

每组测试数据的第一行为两个整数 $n$ 和 $M$,$0<n \leq 20, 0<M<100000$。

再下去的 $n$ 行每行有两个整数 $W_i, P_i$,$0<W_i,P_i<10000$。

输出格式

对于每组测试数据,输出一行,只含一个整数,表示装进去物体的价值最高值。

样例

Input
1
5 10
2 6
2 3
6 5
5 4
4 6
Output
15
不限期开放

题目列表