Trong sứ mệnh khám phá bản đồ, một rô-bốt tự hành được giao một nhiệm vụ di chuyển dọc theo một dãy gồm ~N~ điểm thu thập thông tin, được đánh số từ 1 đến ~N~. Điểm thu thập thông tin ~i~ (~1 \le i \le N~) có lượng dữ liệu là ~A_i~, nếu rô-bốt thu thập thông tin tại điểm này thì sẽ tiêu thụ ~W_i~ năng lượng.

Rô-bốt được lập trình để thu thập các điểm thông tin liên tiếp và phải tuân thủ nghiêm ngặt các điều kiện sau:

• Số lượng điểm thu thập thông tin được quét phải là bội số của ~K~ (để đảm bảo tính toàn vẹn của các gói thông tin);
• Tổng năng lượng tiêu thụ để rô-bốt thu thập thông tin không được vượt quá giới hạn ~S~ của pin. Coi năng lượng tiêu thụ khi di chuyển qua các điểm thông tin bằng 0.

Yêu cầu: Hãy viết chương trình cho rô-bốt để tìm ra các điểm thông tin liên tiếp thỏa mãn điều kiện trên mà tổng lượng dữ liệu thu thập được là lớn nhất.

Input

• Dòng đầu tiên gồm ba số nguyên ~N, K, S~ (~1 \le K \le N \le 10^5~; ~1 \le S \le 10^{12}~);
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~|A_i| \le 10^9~; ~1 \le i \le N~);
• Dòng thứ ba gồm ~N~ số nguyên ~W_1, W_2, \dots, W_N~ (~0 \le W_i \le 10^9~; ~1 \le i \le N~).

Output

• Gồm một số nguyên là lượng dữ liệu thu thập được lớn nhất. Nếu không tồn tại các điểm thông tin liên tiếp khả thi, ghi ra số 0.