Thông tin (Bản 2)

Trong sứ mệnh khám phá bản đồ số, một rô-bốt tự hành được giao 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\).

Tại mỗi điểm \(i\), nếu rô-bốt thu thập thông tin thì sẽ:

• Thu được lượng dữ liệu \(A_i\).
• Tiêu tốn \(W_i\) đơn vị năng lượng.

Rô-bốt được lập trình để chỉ quét 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 phải là bội số của \(K\) (đảm bảo tính toàn vẹn của các gói dữ liệu).
• Tổng năng lượng tiêu thụ không được vượt quá giới hạn \(S\) của pin.
  (Năng lượng tiêu thụ khi di chuyển qua các điểm không thu thập là \(0\).)

Yêu cầu: Hãy viết chương trình để lập trình cho rô-bốt quét một đoạn liên tiếp các điểm sao cho:

• Thỏa mãn cả hai điều kiện ở trên;
• Tổng lượng dữ liệu thu thập được là lớn nhất có thể.

Nếu không tìm được một cách thu thập điểm nào, hoặc tổng lượng dữ liệu lớn nhất thu thập được là số âm thì in ra \(0\).

Input

• Dòng đầu tiên chứa 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 chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(|A_i| \le 10^9\)).
• Dòng thứ ba chứa \(N\) số nguyên \(W_1, W_2, \dots, W_N\) (\(0 \le W_i \le 10^9\)).

Output

• In ra một số nguyên — tổng lượng dữ liệu lớn nhất có thể thu được.

Scoring

• Subtask 1 (25% số điểm): \(N \le 100\).
• Subtask 2 (25% số điểm): \(W_i = 0\) với mọi \(i\).
• Subtask 3 (25% số điểm): \(K = 1\).
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.

Input

5 2 6
3 -1 2 5 -2
2 1 2 2 1

Output

7

Input

3 2 5
10 20 5
1 1 1

Output

30

Notes

Giải thích ví dụ 1:

• Chọn hai điểm liên tiếp là: \(3\) và \(4\).
• Số lượng điểm là \(2\), chia hết cho \(K\);
• Tổng năng lượng: \(2 + 2 = 4 \le 6\);
• Tổng dữ liệu: \(2 + 5 = 7\).

Giải thích ví dụ 2:

• Chọn đoạn \(1\) đến \(2\), dài \(2\), chia hết cho \(K = 2\);
• Năng lượng: \(1 + 1 = 2 \le 5\);
• Tổng dữ liệu: \(10 + 20 = 30\).