Opening a Restaurant

Problem Description

Xiaoming, a graduate of the School of Information, plans to start a business opening restaurants. There are $n$ candidate locations. Xiaoming wants to choose suitable locations to open some restaurants. The $n$ locations lie on a straight line. We use an integer sequence $m_1,m_2,\dots,m_n$ to represent their relative positions. Because of location, the profit of opening a restaurant differs. We use $p_i$ to denote the profit of opening a restaurant at $m_i$. To avoid internal competition among his own restaurants, the distance between any two restaurants must be greater than $k$. Please help Xiaoming choose a plan that maximizes the total profit.

Input Format

The first line of input is an integer $T\ (1\le T\le 1000)$, indicating there are $T$ test cases. The following $T$ test cases are given consecutively. Each test case has $3$ lines.

Line 1: total number of locations $n\ (n<100)$, and distance limit $k\ (k>0$ and $k<1000)$.

Line 2: the positions $m_1,m_2,\dots,m_n$ of the $n$ locations ($1000000>m_i>0$, integers, in ascending order).

Line 3: the restaurant profits $p_1,p_2,\dots,p_n$ at the $n$ locations ($1000>p_i>0$, integers).

Output Format

For each test case, output the maximum possible profit.

Sample Input 1

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

Sample Output 1

40
30

Constraints

$1\le T\le 1000$; $n<100$; $0<k<1000$; $1000000>m_i>0$; $1000>p_i>0$.

Source: "一本通在线评测" (Yiben Tong Online Judge).