Kế hoạch thi đấu

Bạn Nam là một vận động viên quần vợt chuyên nghiệp. Trong hệ thống thi đấu quần vợt, mỗi năm người ta tổ chức n giải đấu đánh số từ 1 đến n. Giải đấu thứ i được tổ chức vào ngày ai và mỗi vận động viên tham gia được khoản tiền thưởng là bi. Tuy nhiên để đảm bảo sức khỏe cho Nam, huấn luyện viên quyết định hai giải đấu mà Nam chọn tham dự phải cách xa nhau ít nhất là k ngày ( |ai - aj| ≥ k) . Bạn hãy giúp Nam chọn lựa các giải thi đấu sao cho tổng số tiền thưởng là nhiều nhất.

Dữ liệu input:

Dữ liệu output:

Ví dụ

input (test 1)

5 2

1 2 3 4 5

1 5 1 5 1

output

10

input

5 2

1 2 3 4 5

1 3 2 1 1

output

4

giải thích :

test1: vì Nam chỉ thi đấu được những ngày cách nhau k ngày (ở test 1 là 2) vì thế nếu ta cho Nam thi đấu bắt đầu từ ngày 1 thì Nam chỉ có thể thi đấu tiếp những ngày 3 và 5 sau đó => Nam được 1 + 1 + 1 = 3 tiền thưởng ,còn nếu Nam bắt đầu thi đấu từ ngày 2 thì Nam chỉ thi đấu được tiếp ngày 4 =>  5 + 5 = 10 tiền thưởng vậy ta sẽ lập lịch cho Nam thi đấu vào ngày 2 và 4 thì sẽ được số tiền thưởng nhiều nhất