Lắp đặt trạm thu phát sóng

Chuẩn bị nghỉ hè, Giáo sư \(X\) quyết định kiểm tra khả năng áp dụng các kiến thức được học của mình trong năm vừa qua bằng một bài toán thực tế.

Ông liên hệ với dự án giả định được mô tả như sau: Dọc trên một tuyến đường người ta muốn lắp đặt các cột thu phát sóng nhằm truyền tiếp các chương trình truyền hình. Hiện tại, các địa điểm có thể đặt các cột thu phát sóng đã được khảo sát và lên danh sách gồm \(n\) địa điểm có tọa độ không giảm \(p_1, p_2, \dots, p_n\).

Theo khảo sát, mỗi địa điểm có khả năng truyền cáp khác nhau và mang lại lợi nhuận tương ứng là \(a_1, a_2, \dots, a_n\). Để các trạm thu phát sóng không gây ảnh hưởng lẫn nhau, khoảng cách giữa hai cột thu phát sóng bất kỳ được chọn không được nhỏ hơn \(k\).

Yêu cầu. Với mỗi bộ test, hãy chọn một số địa điểm để lắp đặt sao cho tổng lợi nhuận thu được là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(T\) (\(T \le 10\)) — số bộ test.
• Mỗi bộ test gồm: - Một dòng chứa hai số nguyên dương \(n, k\) (\(1 \le n \le 10^5\), \(1 \le k \le 10^5\)). - Một dòng chứa \(n\) số nguyên dương \(p_1, p_2, \dots, p_n\) (\(p_i \le 10^6\)) — tọa độ các địa điểm theo thứ tự không giảm. - Một dòng chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^9\)) — lợi nhuận tại các địa điểm tương ứng.

Tổng \(n\) qua tất cả các bộ test không vượt quá \(10^5\).

Output

In ra \(T\) dòng, mỗi dòng là lợi nhuận lớn nhất có thể đạt được với bộ test tương ứng.

Input

%
3
2 1
1 1
1 2
3 2
1 2 3
2 4 3
5 5
1 5 10 15 17
5 20 10 15 25

Output

%
3
5
55

Notes

Ở ví dụ thứ hai, nếu chọn cả vị trí \(1, 2, 3\) thì không hợp lệ vì khoảng cách nhỏ hơn \(2\). Phương án tốt nhất là chọn vị trí \(1\) và \(3\), thu được tổng lợi nhuận là \(2 + 3 = 5\).

Scoring

• (40%) \(n \le 1000\).
• (30%) \(1000 < n \le 10^5\).
• (30%) Không có ràng buộc gì thêm.