Hiring Workers

Interview

Time limit2sMemory limit1024 MB

Summary

Count contiguous groups of workers with equal numbers of task 1 and task 2 workers whose efficiency sums differ by at most K.

Level: Medium5 of 10
Topics: Prefix sum, Hash map, Binary search
Solved: No attempts yet

Problem

Youngsam is playing a simulation game about running a factory. To keep the factory running smoothly, he wants to hire workers.

$N$ workers are standing in a line, and he wants to hire a contiguous group of them. The factory has two kinds of work. The $i$ -th worker can perform only one assigned task $C_i$ , which is either 1 or 2. Each worker also has its own efficiency $W_i$ .

To keep the factory efficient, Youngsam wants to hire workers that satisfy both of the following conditions:

The number of workers performing each task must be the same.
The difference between the sums of efficiencies of the two tasks must be at most $K$ .

Count the number of ways to choose workers so that he can hire them under these conditions.

Input

The first line contains the number of test cases $T$ .

The first line of each test case contains $N$ and $K$ , separated by a space.

The second line contains the task types $C_1, C_2, \cdots, C_N$ in order, separated by spaces.

The third line contains the efficiencies $W_1, W_2, \cdots, W_N$ in order, separated by spaces.

Output

For each test case, print the answer on its own line, in the order of the test cases.

Constraints

All given numbers are integers.
$1 \leq T \leq 10\,000$
$2 \leq N \leq 500\,000$
The sum of $N$ over all test cases is at most $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$ )

Examples1

Example 1

Input

3
3 0
1 2 1
1 1 1
5 4
1 2 2 1 2
8 1 12 8 10
3 10
1 1 1
3 5 6

Expected output

2
3
0