描述

蜗蜗有一个神奇的口袋，口袋可以装下体积总和为 m 的宝石。

一共有 n+1种不同的宝石。第 i (1≤i≤n)种宝石一共有 a[i] 颗，每一颗的体积都是 b[i]（保证 b[i]=2的x次方 ，其中 x是一个正整数）。第 n+1种宝石有无限多颗，每一颗的体积都是1。

现在蜗蜗想用数量最少的宝石装满口袋，请求出蜗蜗最少要使用多少颗宝石。

输入格式

第一行一个正整数 test表示数据组数。

对于每组数据，第一行两个整数 n,m。接下来 n行每行两个整数 ai,bi分别表示一种宝石的数量和体积。

输出格式

对于每组数据，输出一行一个整数，表示蜗蜗最少要使用多少颗宝石。

样例输入

2

2 7

1 2

1 4

2 6

1 2

1 4

样例输出

3

2

数据规模

对于 30%的数据，保证所有的 a[i]=1。

对于 100%的数据，保证1≤test≤10的5次方,1≤n≤31,0≤m<2的31次方,1≤a[i],b[i]<2的31次方，b[i]已经从小到大排好序了并且两两不同。

（附上代码和注释就更好啦）