일꾼 고용

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

현재 $N$명의 일꾼이 일렬로 서 있으며, 영삼이는 이 중 연속한 일꾼들을 고용하려 한다. 공장에는 두 가지 작업이 있으며, $i$번째 일꾼은 미리 배정된 작업 $C_i$만 수행할 수 있다. $C_i$는 1 또는 2이다. 또한 $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$)