THIDAU - Kế hoạch thi đấu
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

        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 nhập:

- Dòng đầu tiên là hai số nguyên n và k cách nhau một khoảng trắng (1 ≤ n ≤ 100, 1 ≤ k ≤ 10)

- Dòng thứ 2 gồm n số nguyên a1, a2, ..., an (1 ≤ ai ≤ 365) là ngày thi đấu của các giải, mỗi số cách nhau một khoảng trắng. Dữ liệu cho đảm bảo a1 < a2 < a3 < ...< an.

- Dòng thứ 3 gồm n số nguyên b1, b2, ..., bn (1 ≤ bi ≤ 100) là số tiền thưởng của từng giải, mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất:

- Là số nguyên xác định số tiền thưởng nhiều nhất mà Nam có thể có được.

Ví dụ

  • input
    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
Back to Top