근무 교대
시간 제한40초메모리 제한1024 MB
각 근무를 두 경비원 중 적어도 한 명이 맡을 때, 두 사람이 각각 H 이상의 행복을 얻는 배정의 수를 센다.
문제
Aninda와 Boon-Nam은 작은 미술관의 경비원이다. 두 사람의 근무는 N번의 교대로 이루어지며, 각 교대마다 두 경비원 중 적어도 한 명은 일해야 한다.
두 경비원은 교대마다 선호도가 다르다. i번째 교대에서 Aninda가 일하면 Ai만큼의 행복 점수를 얻고, Boon-Nam이 일하면 Bi만큼의 행복 점수를 얻는다.
두 경비원이 모두 H점 이상의 행복 점수를 받으면 두 사람은 행복해진다. 두 경비원이 행복해지는 교대 배정의 가짓수는 몇 가지인가?
어떤 교대에서 한 배정에서는 Aninda가 일하고 다른 배정에서는 일하지 않거나, 어떤 교대에서 한 배정에서는 Boon-Nam이 일하고 다른 배정에서는 일하지 않으면 두 배정은 서로 다른 것으로 본다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 교대의 수 N과 필요한 최소 행복 점수 H가 주어진다. 둘째 줄에는 N개의 정수가 주어지며, i번째 정수는 i번째 교대에서 Aninda가 일할 때 얻는 행복 점수 Ai이다. 셋째 줄에는 N개의 정수가 주어지며, i번째 정수는 i번째 교대에서 Boon-Nam이 일할 때 얻는 행복 점수 Bi이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 두 경비원이 행복해지는 교대 배정의 가짓수이다.
제한
- 1 ≤ T ≤ 100.
- 0 ≤ H ≤ 109.
- 0 ≤ Ai ≤ 109.
- 0 ≤ Bi ≤ 109.
힌트
예제 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이다.