Description

欢欢最喜欢小钱钱了。为了搞到更多的小钱钱，欢欢决定转行成为赏金猎人！

赏金猎人的任务是尽可能多地杀掉怪物，这样他才能获得更多的赏金。欢欢初始时有$m$点能量，欢欢将面对一排由$n$只怪物组成的队列。欢欢比较挑剔，他每次只会选择队列中第一个他能够杀死的怪物去击杀。干掉第$i$只怪物需要花费$ai$点能量，同时第$i$只怪物被击杀将会恢复欢欢$bi$点能量。假设欢欢的能量存储没有上限，现在，欢欢想知道他最多能击杀多少只怪物。

Input Format

第一行输入一个正整数$t(1≤t≤10)$，表示共有$t$组测试样例。

对于每组测试样例，第一行输入两个正整数$n,m(1≤n≤100000,1≤m≤10^9)$，表示将会有$n$只怪物。第二行将会输入$n$个正整数$ai(1≤ai≤10^9)$，表示击杀第$i$只怪物所需要消耗的能量。第三行将会输入$n$个正整数$bi(1≤bi≤10^9)$，表示击杀第$i$只怪物欢欢将会恢复的能量。

Output Format

对于每组测试样，输出一行，包含一个正整数，表示欢欢能够击杀的最多的怪物数量。

1
4 1
4 2 1 4
3 2 4 1

3

Hint

首先，欢欢选择击杀第三只怪物，击杀后欢欢能量剩余$4$点。

接着，欢欢选择击杀第一只怪物，击杀后欢欢能量剩余$3$点。

最后，欢欢选择击杀第二只怪物，击杀后欢欢能量剩余$3$点。

此时，欢欢没法继续击杀怪物了，所以答案为$3$。

Source

Online Judge http://127.0.0.1