Description

有一个容量为C(C<=100)的背包以及N(N<=500)颗宝石，第i颗宝石大小为si，价值为vi。由于条件限制，
你手边只有这个背包可作为你搬运宝石的唯一工具。现在你想知道在最多可以带走多大价值的宝石。

Input

第一行输入M(M<=10)表示有M组数据。每组数据第一行输入N、C，表示宝石数目以及背包容
量；接下来一行输入N组(si,vi), si和vi均为整数，表示每颗宝石的大小和价值。

Output

输出M行正整数，第i行表示第i组数据可以带走的宝石的最大代价, 背包可不用装满。

Sample Input

3
3 10
1 3 2 5 7 2
3 10
1 3 2 5 6 2
5 10
5 6 5 7 2 8 8 1 5 9

Sample Output

10
10
17