题目描述

一条直线上有 $n$ 个候选地点，第 $i$ 个地点的位置为 $m_i$，在这里开餐馆可以获得 $p_i$ 的利润。

为了避免餐馆之间相互竞争，任意两家餐馆之间的距离必须大于 $k$。请计算可以获得的最大总利润。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

每组数据包含三行：

• 第一行包含两个整数 $n,k$；
• 第二行包含 $n$ 个严格递增的正整数 $m_1,m_2,\ldots,m_n$，表示候选地点的位置；
• 第三行包含 $n$ 个正整数 $p_1,p_2,\ldots,p_n$，表示在各地点开餐馆的利润。

输出格式

对于每组数据，输出一行一个整数，表示最大总利润。

样例

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

40
30

数据范围与提示

• $1 \le T \le 1000$
• $1 \le n < 100$
• $k > 0$
• $m_i > 0$
• $0 < p_i < 1000$