KẾ HOẠCH THI ĐẤU

 1. CẤU TRÚC ĐỀ BÀI

• Tên bài: KẾ HOẠCH THI ĐẤU
• Mã bài: PLAN
• File chương trình: PLAN.PY
• File dữ liệu: PLAN.INP
• File kết quả: PLAN.OUT

2. Dẫn dắt

Nam là một vận động viên quần vợt chuyên nghiệp. Mùa giải này có N giải đấu được tổ chức. Giải đấu thứ i diễn ra vào ngày Ai và nếu tham gia, Nam sẽ nhận được điểm thưởng là Bi.

Để đảm bảo sức khỏe hồi phục, huấn luyện viên quy định: Nếu Nam tham gia 2 giải đấu bất kỳ, thì ngày tổ chức của chúng phải cách nhau ít nhất K ngày.

3. Yêu cầu

Hãy giúp Nam lựa chọn các giải đấu để tham gia sao cho tổng điểm thưởng thu được là lớn nhất.

4. Dữ liệu (Input)

• Dòng 1: Hai số nguyên N và K (1 ≤ N ≤ 100.000, 1 ≤ K ≤ 100).
• Dòng 2: N số nguyên A1, A2, ..., AN là ngày thi đấu (1 ≤ Ai ≤ 10⁹). Dữ liệu đảm bảo ngày thi đấu tăng dần.
• Dòng 3: N số nguyên B1, B2, ..., BN là điểm thưởng (1 ≤ Bi ≤ 10⁴).

5. Kết quả (Output)

• Ghi ra một số nguyên duy nhất là tổng điểm thưởng lớn nhất.

6. Ví dụ

PLAN.INP	PLAN.OUT	Giải thích
5 2 1 2 3 4 5 1 5 1 5 1	10	Chọn giải 2 (ngày 2, điểm 5) và giải 4 (ngày 4, điểm 5). Khoảng cách ngày: 4 - 2 = 2 (thỏa mãn ≥ K). Tổng điểm: 5 + 5 = 10.

7. Ràng buộc 

• 50% số test: N ≤ 5.000 
• 100% số test: N ≤ 100.000. 1 ≤ K ≤ 100; Ngày thi đấu ≤ 10⁹; Điểm thưởng ≤ 10⁴ 

Tải test chấm Themis