32125번 - 일꾼 고용 서브태스크

문제

영삼이는 공장을 운영하는 시뮬레이션 게임을 하고 있다. 영삼이는 공장을 원활하게 운영하기 위해 일꾼을 고용하려 한다.

현재 $N$명의 일꾼이 일렬로 줄을 서 있으며, 이 중 연속된 일련의 일꾼들을 고용하고자 한다. 공장에는 두 가지 단계의 다른 작업이 있으며, $i$번째 일꾼은 두 가지 작업 중 미리 배정된 하나의 작업 $C_i$만을 수행할 수 있다. 또한, $i$번째 일꾼은 고유한 능률 $W_i$을 가지고 있다.

영삼이는 공장 운영의 효율성을 위해 다음과 같은 조건을 만족하는 일꾼들을 고용하려 한다:

• 각 작업을 수행하는 일꾼의 수가 동일해야 한다.
• 두 작업의 일꾼의 능률 합의 차이가 $K$ 이하가 되어야 한다.

영삼이를 위해서 이 조건을 만족하면서 고용할 수 있도록 일꾼을 선택하는 방법의 개수를 구해주자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 $N$과 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에는 일꾼의 작업 유형 $C_1, C_2, \cdots, C_N$이 차례대로 공백으로 구분되어 주어진다.

세 번째 줄에는 일꾼의 능률 $W_1, W_2, \cdots, W_N$이 차례대로 공백으로 구분되어 주어진다.

출력

각 테스트 케이스의 정답을 한 줄에 하나씩 차례대로 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• 1ドル \leq T \leq 10,000円$
• 2ドル \leq N \leq 500,000円$
• 모든 테스트 케이스에서 $N$의 합은 500ドル,000円$ 이하이다.
• 0ドル \leq K \leq 10^9$
• 1ドル \leq C_i \leq 2$ (1ドル \leq i \leq N$)
• 0ドル \leq W_i \leq 10^9$ (1ドル \leq i \leq N$)

서브태스크

힌트