THỰC HÀNH

Trang trại nhà Hoa trồng nhiều nhãn, mùa nhãn đang đến, nhãn đã chín rất đều mà chưa kịp thu hoạch, bỗng dưng một cơn bão sắp kéo đến có nguy cơ tàn phá hết số nhãn, bố mẹ Hoa đang rất lo lắng thì chợt có một ông Bụt hiện ra và nói với Hoa: “Ta cho con một cái túi thần và một câu thần chú, con hãy đứng một chỗ, cầm túi và niệm chú, tất cả các quả nhãn ở những cây cách chỗ con đứng không quá L mét sẽ tự động bay hết vào túi thần này”. Hoa mừng quá nhưng chưa biết nếu Hoa chọn được chỗ đứng tốt nhất thì số nhãn thu được tối đa là bao nhiêu? Em hãy giúp Hoa làm việc đó nhé.

Cho biết trang trại nhà Hoa có N cây nhãn trồng thành một hàng, khoảng cách giữa hai cây nhãn liên tiếp là K mét, số lượng nhãn trên các cây lần lượt là a₁, a₂, …, a_N. Em hãy giúp Hoa tính xem với phép màu của ông Bụt thì Hoa có thể thu hoạch được tối đa bao nhiêu nhãn (Phép màu chỉ có hiệu lực đúng một lần).

Dữ liệu vào:

• Dòng đầu là ba số nguyên dương N, K, L lần lượt là số cây nhãn, khoảng cách giữa hai cây nhãn liên tiếp và bán kính hiệu lực của phép màu.
• Dòng thứ 2 gồm N số nguyên không âm a₁, a₂, …, a_N là số lượng nhãn của các cây nhãn, mỗi số cách nhau bởi một khoảng trống.

Dữ liệu ra:

Một số nguyên duy nhất là số nhãn tối đa thu hoạch được.

Ví dụ:

Dữ liệu vào:
6 2 3
4 2 4 5 1 6

Dữ liệu ra:
16

Giải thích: Đứng ở giữa cây nhãn số 4 và số 5 thì sẽ thu được số nhãn ở các cây số 3, 4, 5, 6 với tổng số lượng nhãn là 4 + 5 + 1 + 6 = 16 (lớn nhất)

Giới hạn:

• 60% số test (ứng với 60% số điểm của bài) 1 ≤ N, K, L, a_i ≤ 300.
• 40% số test (ứng với 30% số điểm của bài) 1 ≤ N ≤ 10⁶, 1 ≤ K, L, a_i ≤ 10⁹.