g6-08134. 进货几趟 未做

小吴开的水果店今天要跑 $T$ 趟进货。每趟列出 $n$ 种水果和这一趟的车厢容量 $W$：第 $i$ 种水果每箱占 $w_i$ 个单位空间、能卖 $v_i$ 元，每种都货源充足，想进几箱进几箱。

每趟单独计算，求每趟最多能赚到多少利润，按趟输出。

第一行一个整数 $T$。

接下来依次是 $T$ 组数据，每组数据为：

第一行两个整数 $n$、$W$；

接下来 $n$ 行，每行两个整数 $w_i$、$v_i$。

输出 $T$ 行，每行一个整数，依次为每组问题的答案。

输入 1

2
3 10
2 3
3 4
4 5
1 5
2 7

输出 1

15
14

第一趟进 5 箱每箱占 2 个单位、能卖 3 元的水果：共占 $2\times 5=10$ 个单位，能卖 $3\times 5=15$ 元。第二趟只有一种每箱占 2 个单位、能卖 7 元的水果，车厢只装得下 2 箱，能卖 $7\times 2=14$ 元。

$1\le T\le 5$，$1\le n\le 2000$，$0\le W\le 2\times 10^4$，$1\le w_i\le 10^9$，$0\le v_i\le 10^9$，且所有组满足 $\sum n_i\times W_i\le 2\times 10^7$。保证答案不超过 $10^{18}$。