23949번 - Shifts 서브태스크다국어

문제

Aninda and Boon-Nam are security guards at a small art museum. Their job consists of N shifts. During each shift, at least one of the two guards must work.

The two guards have different preferences for each shift. For the i-th shift, Aninda will gain A_i happiness points if he works, while Boon-Nam will gain B_i happiness points if she works.

The two guards will be happy if both of them receive at least H happiness points. How many different assignments of shifts are there where the guards will be happy?

Two assignments are considered different if there is a shift where Aninda works in one assignment but not in the other, or there is a shift where Boon-Nam works in one assignment but not in the other.

입력

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and H, the number of shifts and the minimum happiness points required, respectively. The second line contains N integers. The i-th of these integers is A_i, the amount of happiness points Aninda gets if he works during the i-th shift. The third line contains N integers. The i-th of these integers is B_i, the amount of happiness points Boon-Nam gets if she works during the i-th shift.

출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of different assignments of shifts where the guards will be happy.

제한

• 1 ≤ T ≤ 100.
• 0 ≤ H ≤ 10⁹.
• 0 ≤ A_i ≤ 10⁹.
• 0 ≤ B_i ≤ 10⁹.

Test Set 1 (20점)

• 1 ≤ N ≤ 12.

Test Set 2 (23점)

• 1 ≤ N ≤ 20.

힌트

In Sample Case #1, there are N = 2 shifts and H = 3. There are three possible ways for both Aninda and Boon-Nam to be happy:

• Only Aninda works on the first shift, while both Aninda and Boon-Nam work on the second shift.
• Aninda and Boon-Nam work on the first shift, while only Aninda works on the second shift.
• Both security guards work on both shifts.

In Sample Case #2, there are N = 2 shifts and H = 5. It is impossible for both Aninda and Boon-Nam to be happy, so the answer is 0.