Điểm:
100 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Nam là một vận động viên quần vợt chuyên nghiệp. Trong một hệ thống thi đấu quần vợt, 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 thứ \( a_i \) (ngày Ban tổ chức ra quyết định là ngày thứ 1) và mỗi vận động viên tham gia được cộng điểm thưởng là \( b_i \). Để đảm bảo sức khỏe, 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 (\(|a_i - a_j| \geq k\) nếu Nam tham dự cả giải thứ \( i \) và giải thứ \( j \)).
Bạn hãy giúp Nam chọn lựa các giải thi đấu sao cho tổng số điểm thưởng là nhiều nhất.
Dữ liệu:
- Dòng đầu tiên là hai số nguyên \( n \) và \( k \) (\( 1 \leq n \leq 10^5, 1 \leq k \leq 100 \))
- Dòng thứ hai chứa \( n \) số nguyên \( a_1, a_2, ..., a_n \) (\( 1 \leq a_i \leq 10^9 \)) là ngày thi đấu của các giải 1, 2, ..., \( n \). Dữ liệu cho đảm bảo \( a_1 < a_2 < a_3 < ... < a_n \).
- Dòng thứ ba chứa \( n \) số nguyên \( b_1, b_2, \dots, b_n \) (\( 1 \leq b_i \leq 10^4 \)) là số điểm thưởng của các giải 1, 2, ..., \( n \).
Kết quả:
- Một số nguyên duy nhất là tổng số điểm thưởng lớn nhất mà Nam có thể có được.
Ví dụ:
INPUT | OUTPUT |
---|---|
5 2 | 10 |
1 2 3 4 5 | |
1 5 1 5 1 |
Ghi chú:
- 50% test có \( n \leq 5000 \)
- 50% test có \( 5000 < n \leq 10^5 \)
Bình luận