Description

Xiao Ming, a student from the School of Information, plans to start a restaurant business after graduation. There are currently $n$ locations to choose from, and Xiao Ming intends to select suitable spots to open some restaurants.
These $n$ locations are arranged in a straight line. Their relative positions are represented by an integer sequence $m_1, m_2, \dots, m_n$.
Due to varying地段 (location) factors, the profits from opening restaurants differ. We use $p_i$ to denote the profit from opening a restaurant at $m_i$. To avoid internal competition among his restaurants, the distance between any two restaurants must be greater than $k$. Please help Xiao Ming select a plan that maximizes the total profit.

Input Format

The first line of input is an integer $T$ ($1 \leq T \leq 1000$), indicating there are $T$ test cases. This is followed by $T$ consecutive test cases. Each test case consists of $3$ lines:

• Line 1: The total number of locations $n$ ($n < 100$) and the distance restriction $k$ ($k > 0$ and $k < 1000$);
• Line 2: The positions of the $n$ locations $m_1, m_2, \dots, m_n$ ($1000000 > m_i > 0$ and integers, listed in ascending order);
• Line 3: The profits of opening restaurants at the $n$ locations $p_1, p_2, \dots, p_n$ ($1000 > p_i > 0$ and integers).

Output Format

For each test case, output the maximum possible profit.

2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30

40
30