교대 근무

Aninda와 Boon-Nam은 작은 미술관의 경비원이다. 이들의 업무는 N개의 교대 근무로 이루어진다. 각 교대 근무에는 두 경비원 중 적어도 한 명이 일해야 한다.

두 경비원은 각 교대 근무에 대해 서로 다른 선호도를 가진다. i번째 교대 근무에서 Aninda가 일하면 행복 점수 $A_{i}$점을 얻고, Boon-Nam이 일하면 행복 점수 $B_{i}$점을 얻는다.

두 경비원은 둘 다 적어도 H점의 행복 점수를 얻으면 행복해진다. 경비원들이 행복해지는 서로 다른 교대 근무 배정은 몇 가지인가?

어떤 교대 근무에서 한 배정에는 Aninda가 일하지만 다른 배정에는 일하지 않거나, 어떤 교대 근무에서 한 배정에는 Boon-Nam이 일하지만 다른 배정에는 일하지 않으면 두 배정은 서로 다른 것으로 간주한다.

제한

시간 제한: 테스트 세트당 40초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 0 ≤ H ≤ $10^{9}$. 0 ≤ $A_{i}$ ≤ $10^{9}$. 0 ≤ $B_{i}$ ≤ $10^{9}$.

테스트 세트 1 (공개)

1 ≤ N ≤ 12.

테스트 세트 2 (비공개)

1 ≤ N ≤ 20.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 교대 근무 수와 필요한 최소 행복 점수를 각각 나타내는 두 정수 N과 H가 포함된 줄로 시작한다. 두 번째 줄에는 N개의 정수가 주어진다. 이 정수들 중 i번째 정수는 $A_{i}$이며, Aninda가 i번째 교대 근무에서 일할 경우 얻는 행복 점수이다. 세 번째 줄에는 N개의 정수가 주어진다. 이 정수들 중 i번째 정수는 $B_{i}$이며, Boon-Nam이 i번째 교대 근무에서 일할 경우 얻는 행복 점수이다.

각 테스트 케이스에 대해 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이고(1부터 시작), y은 경비원들이 행복해지는 서로 다른 교대 근무 배정의 수이다.

예제 케이스 #1에서 교대 근무 수는 N = 2이고 H = 3이다. Aninda와 Boon-Nam이 둘 다 행복해질 수 있는 방법은 다음과 같이 세 가지이다.

• 첫 번째 교대 근무에는 Aninda만 일하고, 두 번째 교대 근무에는 Aninda와 Boon-Nam이 둘 다 일한다.

• 첫 번째 교대 근무에는 Aninda와 Boon-Nam이 일하고, 두 번째 교대 근무에는 Aninda만 일한다.

• 두 경비원 모두 두 교대 근무에서 모두 일한다.

예제 케이스 #2에서 교대 근무 수는 N = 2이고 H = 5이다. Aninda와 Boon-Nam이 둘 다 행복해지는 것은 불가능하므로 답은 0이다.