Bão mặt trời là hiện tượng mặt trời hoạt động mạnh, gây ra sự biến đổi đột ngột của điện từ trường. Khi đến trái đất, nó có thể gây hậu quả tiêu cực, ảnh hưởng đến sức khỏe con người, hoạt động sống của động vật, thực vật, cũng như các thiết bị điện tử và hệ thống 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ơn bão này sẽ phá hủy toàn bộ các trạm không được bảo vệ. Để chuẩn bị, người ta đã chế tạo ra \(K\) thiết bị bảo vệ, mỗi thiết bị có khả năng bảo vệ một vùng không gian bán kính \(R\) (theo đơn vị khoảng cách trên đường thẳng). Mỗi thiết bị phải được đặt tại đúng vị trí của một trạm thám hiểm nào đó, không được đặt ngoài không gian. Mỗi trạm có thể đặt nhiều thiết bị.

Hệ thống trạm thám hiểm được mô hình hóa như một đường thẳng một chiều. Các trạm được đánh số từ \(1\) đến \(N\) từ trái qua phải, trạm thứ \(i\) nằm ở vị trí tọa độ \(x_i\) và có giá trị sử dụng \(v_i\). Một trạm \(j\) được coi là được bảo vệ nếu tồn tại ít nhất một thiết bị đặt tại trạm \(i\) sao cho \(|x_i - x_j| \leq R\).

Sau cơn bão, các trạm không được bảo vệ sẽ bị phá hủy, làm mất liên kết với các trạm còn lại. Giá trị sử dụng còn lại của hệ thống được tính bằng tổng giá trị lớn nhất của một đoạn liên tiếp các trạm còn sống sót (các trạm liên tiếp nhau trong hệ thống ban đầu và đều được bảo vệ).

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

Input

• Dòng đầu tiên gồm ba số nguyên dương \(N, K, R\):
  • \(1 \le N, K \le 10^6\)
  • \(1 \le R \le 10^{12}\)
• Dòng tiếp theo ghi \(N-1\) số nguyên dương \(d_i\) \((1 \le d_i \le 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 \le v_i \le 10^6)\) là giá trị sử dụng của các trạm \(i\).

Output

• Ghi ra 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.

Example

6 2 7
10 4 7 18 11
5 8 2 4 8 12

22

6 1 38
10 4 7 18 11
5 8 2 4 8 12

39

Scoring

• Subtask \(1\) (\(10\%\) đ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\%\) điểm): \(K = 1\), \(d_i = 1\).
• Subtask \(3\) (\(11\%\) điểm): \(K = 1\).
• Subtask \(4\) (\(8\%\) điểm): \(K = 1\), \(d_i = 2\).
• Subtask \(5\) (\(18\%\) điểm): \(N \le 10^4\).
• Subtask \(6\) (\(16\%\) điểm): \(K \le 50\).
• Subtask \(7\) (\(30\%\) điểm): không có thêm ràng buộc gì.