Không gian

Bão mặt trời là thời điểm mặt trời hoạt động mạnh, dẫn đến sự biến đổi đột ngột của điện từ trường, khi gửi đến trái đất có thể gây ra những hậu quả tiêu cực ảnh hưởng đến sức khỏe, hoạt động sống của động vật, thực vật, thiết bị điện tử, viễn thông,...

Hệ thống trạm thám hiểm không gian quốc tế sắp đối mặt với cơn bão mặt trời cực lớn, có nguy cơ phá hủy một số trạm thám hiểm nếu nó không được bảo vệ. Người ta đã chế tạo ra $K$ thiết bị, mỗi thiết bị có khả năng bảo vệ một vùng không gian bán kính $R$: thiết bị đặt tại một trạm bảo vệ mọi trạm có khoảng cách tới trạm đó không vượt quá $R$. Thiết bị bảo vệ phải được đặt tại trạm thám hiểm, chứ không đặt ngoài không gian. Có thể dùng không quá $K$ thiết bị.

Hệ thống trạm thám hiểm được coi như nằm trên một đường thẳng, các trạm được đánh số từ $1$ đến $N$ từ trái qua phải, trạm thứ $i$ có giá trị sử dụng $v_i$. Các trạm không được bảo vệ sẽ bị phá hủy. Khi một số trạm bị phá hủy sẽ gây mất liên kết với các trạm còn lại, khi đó giá trị sử dụng còn lại của hệ thống là giá trị lớn nhất của một cụm nào đó mà còn liên kết được với nhau (giá trị của một cụm là tổng giá trị sử dụng của các trạm trong cụm); các trạm còn liên kết được với nhau là các trạm liên tiếp trong hệ thống ban đầu và đều không bị phá hủy.

Yêu cầu: Hãy đặt các thiết bị sao cho giá trị sử dụng còn lại của hệ thống là lớn nhất.

Dữ liệu vào

• Dòng đầu tiên là ba số nguyên dương $N,K,R$ ($1\le N,K\le {10}^6$, $1\le R\le {10}^{12}$) là số trạm thám hiểm, số thiết bị bảo vệ, bán kính bảo vệ của mỗi thiết bị.
• Dòng tiếp theo ghi $N-1$ số nguyên dương $d_1,d_2,\dots ,d_{N-1}$ ($1\le d_i\le {10}^6$), $d_i$ là khoảng cách từ trạm $i$ tới trạm $i+1$ (dòng này để trống khi $N=1$).
• Dòng tiếp theo ghi $N$ số nguyên dương $v_1,v_2,\dots ,v_N$ ($1\le v_i\le {10}^6$) là giá trị sử dụng của các trạm.

Dữ liệu ra

In ra một số nguyên là giá trị sử dụng còn lại nhiều nhất của các trạm thám hiểm liên tiếp còn lại sau cơn bão mặt trời.

Ràng buộc

• $1\le N,K\le {10}^6$.
• $1\le R\le {10}^{12}$.
• $1\le d_i\le {10}^6$, $1\le v_i\le {10}^6$.

Subtasks

• Subtask 1 ($10\%$ số điểm): $K=1$, $N\le {10}^4$, $R\le {10}^9$, $d_i\le {10}^5$, $v_i\le {10}^5$.
• Subtask 2 ($7\%$ số điểm): $K=1$, $d_i=1$.
• Subtask 3 ($11\%$ số điểm): $K=1$.
• Subtask 4 ($8\%$ số điểm): $K=1$, $d_i=2$.
• Subtask 5 ($18\%$ số điểm): $N\le {10}^4$.
• Subtask 6 ($16\%$ số điểm): $K\le 50$.
• Subtask 7 ($30\%$ số điểm): Không có ràng buộc gì thêm.

Ví dụ