g6-08094. 多次进货 未做

小超市这周要分 $T$ 次进货。每次进货给出 $n$ 种商品，第 $i$ 种每件重 $w_i$、价值 $v_i$，同一种商品供应商都管够，想进几件就进几件；这一趟货车最多装 $V$。请逐次算出一车货能带来的最大总价值。

第一行一个整数 $T$。接下来 $T$ 组，每组第一行两个整数 $n,V$；随后 $n$ 行，每行两个整数 $w_i,v_i$。

$T$ 行，每行一个整数，依次表示每组数据的最大总价值。

输入 1

2
1 6
2 3
2 5
1 2
2 3

输出 1

9
10

第一批只有一种商品，进三件正好重 $2\times 3=6$，价值 $3\times 3=9$；第二批进五件重 1、价值 2 的商品，价值 $2\times 5=10$。

$1\le T\le 50$，$1\le n\le 60$，$0\le V\le 500$，$1\le w_i\le 10^9$，$0\le v_i\le 10^9$，答案不超过 $10^{18}$。