Problem 1088 --我们遇到什么困难也不要怕

1088: 我们遇到什么困难也不要怕

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 140  Solved: 36
[Submit][Status][Web Board][Creator:]

Description

我向佛祖许愿,希望群里所有的朋友开心

佛说:“不行, 只能

我说:“, 春天夏天秋天冬天

佛说:“不行, 只能

我说:“, 昨天、今天、明天”

佛说:“不行, 只能两天”

我说:“行, 那就白天、黑天(指夜晚)”

佛哭了, 说:“行吧”

于是由于我邪恶的许愿, 群里的1~n位朋友们在明天的白天和夜晚这两个时段中, 必须至少有一个时段不开心. 每个群友都有自己的两个郁闷能量aiai,bibi, 分别表示编号为i的群友若在白天不开心和夜晚不开心所收获的郁闷值. 邪恶的我认为, 只有群友们在白天郁闷值的总和与夜晚郁闷值的总和都大等于h, 群友们才是真正的都不开心.

佛茫然地望着你, 请你告诉佛祖有多少种群友不开心的方案能满足这个邪恶许愿?

Input

多组测试样例,第一行一个整数T,表示测试样例组数。0<T<=100

每组测试样例包括三行

第一行为题目中描述的n h, 1<=n<=12, 0<=h<=1,000,000

第二行为n个非负整数, {aiai} 意义如题目描述, 0<=aiai<=100,000

第三行为n个非负整数, {bibi} 意义如题目描述, 0<=bibi<=100,000


Output

输出共T行, 每行一个整数, 代表能满足邪恶许愿的方案数.

Sample Input

2
2 3
1 2
3 3
2 5
2 2
10 30

Sample Output

3
0

HINT

对于第一个样例:
有三种办法让两位群友达到邪恶要求:
1. 两位群友在白天都不开心, 夜晚只有群友1不开心
2. 两位群友在白天都不开心, 夜晚只有群友2不开心
3. 两位群友在白天夜晚都不开心
对于第二个样例:
没有方案能满足邪恶要求

Source

[Submit][Status]