题目描述

一条直线上有n个可供开餐馆的地点，位置依次为m_1至m_n，在第i个位置开餐馆可以获得利润p_i。

为了避免竞争，任意两家所选餐馆之间的距离必须严格大于k。求可以获得的最大总利润。

输入格式

第一行整数T，表示数据组数。每组有三行：第一行n、k；第二行n个按升序排列的位置；第三行n个对应的利润。

输出格式

每组输出一行，表示最大总利润。

样例

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

40
30

数据范围

1≤T≤1000，1≤n<100，1≤k<1000；0<m_i<1000000，位置互不相同且升序排列；0<p_i<1000。