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 đến ả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ị bảo vệ phải được đặt tại trạm thám hiểm, chứ không đặt ngoài không gian.

Hệ thống trạm thám hiểm được đặt coi như một đường thẳng, các trạm được đánh số từ \(\mathbf{1}\) đến \(\mathbf{N}\) từ trái qua phải, trạm thứ \(\mathbf{i}\ \)có giá trị sử dụng \(\mathbf{v}_{\mathbf{i}}\). 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, 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.

Dữ liệu vào:

+ Dòng đầu tiên là ba số nguyên dương \(N,\ K,\ R\ (1 \leq N,\ K \leq 10^{6},\ 1 \leq R \leq 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_{i}(1 \leq d_{i} \leq 10^{6})\ \)là khoảng cách trạm \(i\) với trạm \(i + 1.\ \)

+ Dòng tiếp theo ghi \(N\) số nguyên dương \(v_{i}\ (1 \leq v_{i} \leq 10^{6})\) là giá trị của sử dụng của các trạm \(i\).

Kết quả:

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.

Ví dụ:

Ràng buộc:

Subtask 1: 10% điểm có \(K = 1,\ N \leq 10^{4},\ R \leq 10^{9},\ d_{i} \leq 10^{5},\ v_{i} \leq 10^{5};\)

Subtask 2: 7% điểm có \(K = 1,\ d_{i} = 1;\)

Subtask 3: 11% điểm có \(K = 1;\)

Subtask 4: 8% điểm có \(K = 1,\ d_{i} = 2\);

Subtask 5: 18% điểm \(N \leq 10^{4};\)

Subtask 6: 16% điểm có \(K \leq 50\);

Subtask 7: 30% điểm còn lại không có thêm ràng buộc gì.