逃离地球

魔法师小明通过占卜，得知了地球马上就要毁灭，于是他准备了一艘飞船准备逃离地球。由于小明的物品实在是太多，无法全部装入飞船，于是他进行挑选。

小明拥有n个物品，每个物品在小明心中有一个价值ci, 同时每个物品有个体积vi。小明飞船的容量为V, 同时小明希望能最大化所携带的物品的价值之和。

[输入说明]

首先输入组数T. (T<=40)

每组数据输入物品个数n和飞船的容量V.

接下来的n行，输入两个整数vi和 ci (1<= v <= 1000000, 1<= ci <= 100)

对于30%的数据， n <= 10;

对于60%的数据， n <= 50; V <= $10^4$

对于100%的数据, n <= 100, V <= $10^8 $

输出小明最大能携带的物品的价值之和。